GrafMenengahFase D–FE1E5

Bellman-Ford

Bellman-Ford mencari jalur terpendek dari satu sumber dengan merelaksasi SEMUA sisi sebanyak V-1 kali. Berbeda dari Dijkstra, ia menangani bobot negatif dan bisa mendeteksi siklus negatif. Lebih lambat, tapi lebih umum.

Contoh kasus

Rute dengan biaya bisa negatif (mis. subsidi atau diskon di ruas tertentu) yang tak bisa ditangani Dijkstra.

Silabus

Bellman-Ford mencari jalur terpendek dengan me-relaksasi semua sisi berkali-kali, dan sanggup menangani bobot negatif yang tak bisa dipakai Dijkstra.

Tujuan Belajar

·Memahami proses relaksasi semua sisi sebanyak V-1 kali
·Menjelaskan kelebihan Bellman-Ford saat ada bobot negatif
·Menerapkan deteksi siklus negatif pada graf

Cara Kerja

·Awali jarak semua simpul sebagai tak hingga kecuali sumber = 0
·Relaksasi setiap sisi: perbarui jarak tujuan bila lewat sisi itu lebih murah
·Ulangi relaksasi semua sisi sebanyak V-1 kali
·Bila masih ada jarak yang bisa turun pada iterasi ekstra, berarti ada siklus negatif
·Hasil akhir adalah jarak terpendek dari sumber ke semua simpul

Prasyarat

·Graf berbobot
·Dijkstra

Contoh Nyata

·Rute yang punya diskon atau subsidi di ruas tertentu (biaya bisa minus)
·Cari peluang tukar mata uang yang untung berulang di aplikasi trading
·Hitung ongkos jaringan saat sebagian jalur justru menambah saldo

Kompleksitas O(V x E)