Penentuan Path Terpendek Dengan Algoritme Dekomposisi Jarvis-Tufekci

Abstract

Salah satu masalah arus dalam suatu network adalah penentuan path terpendek. Masalah path terpendek ini merupakan masalah pengoptimuman, karena dengan diperolehnya path terpendek diharapkan dapat mengoptimumkan faktor yang lain (misalkan: waktu dan biaya). Secara umum, masalah path terpendek dalam suatu network ini terbagi menjadi 3 tipe, yakni menentukan (1) path terpendek antara suatu simpul dan simpul lainnya, (2) path terpendek antara suatu simpul dengan semua simpul lainnya, dan (3) path terpendek antara semua pasang simpul yang terdapat pada network tersebut. Salah satu algoritme yang dapat digunakan untuk menentukan path terpendek tipe (1) yakni path terpendek antara suatu simpul dan simpul lainnya adalah algoritme dekomposisi Jarvis- Tufekci. Dalam karya ilmiah ini kedua simpul tersebut masing-masing adalah simpul source (sumber) dan sink (tujuan). Tahapan yang dilakukan dalam algoritme ini adalah mendekomposisi suatu network yang diberikan menjadi beberapa buah subnetwork yang bertindih secara linear (linearly overlapping). Lima tahap utama akan dilakukan dalam menyelesaikan masalah path terpendek dengan algoritme dekomposisi Jarvis-Tufekci ini. Berdasarkan seluruh tahapan algoritme dekomposisi Jarvis-Tufekci ini juga akan dilakukan penghitungan kompleksitasnya.