Kedua-duanya mencari jalan terpendek dari sumber dalam graf berwajaran. Dijkstra lebih cepat tetapi memerlukan bobot bukan negatif; Bellman-Ford lebih perlahan tetapi menangani tepi negatif dan mengesan kitaran negatif.
Berulang kali luaskan nod yang tidak dilawati paling dekat dan santaikan jirannya.
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
Santaikan semua tepi V-1 kali; santaian lanjut bermakna kitaran negatif.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Bobot | bukan negatif | apa saja (termasuk negatif) |
| Masa | O((V+E) log V) | O(V·E) |
| Kitaran neg. | n/a | mengesan |
Gunakan Dijkstra secara lalai untuk bobot bukan negatif (peta, rangkaian). Gunakan Bellman-Ford apabila tepi negatif wujud (cth., arbitraj). Dijkstra putus diam pada bobot negatif — perangkap klasik.
Algoritma jalan-terpendek memacu penghalaan, pelayaran, protokol rangkaian, dan analisis kos pergantungan.
Mengetahui kekangan bobot bukan-negatif pada Dijkstra mengelakkan jawapan yang salah di lapangan.
Ide santaian menghubungkan pemikiran greedy dan DP, menjadikannya topik kaya peringkat senior.