24
•
Kapasitas aliran, yaitu batas aliran yang fisibel pada busur tertentu.
•
Sumber, yaitu node yang menjadi awal dari busur-busurnya.
•
Tujuan, yaitu node yang menjadi tujuan busur-busurnya.
2.8.3.1 Persoalan Rute
Terpendek
Untuk setiap dua node S dan T dapat terjadi beberapa lintasan, dimana lintasan
dengan bobot yang minimum disebut sebagai lintasan atau rute terpendek. Bobot di sini
dapat berupa jarak, waktu tempuh, atau ongkos transportasi dari satu node ke node yang
lainnya yang membentuk rute tertentu.
Algoritma mencari rute terpendek ini dikembangkan oleh Djikstra. Algoritma tersebut
digunakan apabila semua busur jaringan mempunyai bobot positif. Langkah-langkah
penyelesaiannya yaitu :
1) Buatlah tabel seperti dibawah ini :
Tabel
2.1 Tabel
Penyelesaian
Algoritma
Dijkstra
2) Isilah baris node dengan seluruh node yang ada, dan baris bobot dengan nilai ~
sebagai nilai awal.
3) Pilihlah node awal (misal node A) untuk diseleksi
4) Carilah node yang berhubungan dengan node A (misal node B dan C).
 |