Keduanya menemukan jalur terpendek dari sumber dalam graf berbobot. Dijkstra lebih cepat tetapi memerlukan bobot non-negatif ; Bellman-Ford lebih lambat tetapi menangani tepi negatif dan mendeteksi siklus negatif.
Secara berulang perluas simpul yang tidak dikunjungi terdekat dan relaksasi tetangganya.
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
Relaksasi semua tepi V-1 kali; relaksasi lebih lanjut berarti siklus negatif.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Bobot | non-negatif | apa saja (termasuk negatif) |
| Waktu | O((V+E) log V) | O(V·E) |
| Siklus neg. | n/a | mendeteksinya |
Gunakan Dijkstra secara default untuk bobot non-negatif (peta, jaringan). Gunakan Bellman-Ford ketika tepi negatif ada (misalnya, arbitrase). Dijkstra diam-diam gagal pada bobot negatif — jebakan klasik.
Algoritma jalur terpendek menjalankan routing, navigasi, protokol jaringan, dan analisis biaya ketergantungan.
Mengetahui batasan bobot non-negatif pada Dijkstra mencegah jawaban yang salah di lapangan.
Ide relaksasi menghubungkan pemikiran greedy dan DP, menjadikannya topik kaya tingkat senior.