Loro-lorone golek dalan paling cepet saka sumber ing graf sing bobote. Dijkstra luwih cepet nanging butuh bobot ora negatif; Bellman-Ford luwih alon nanging bisa nangani sisik negatif lan ndeteksi siklus negatif.
Balekna palawahe simpul sing durung diunggali sing paling cedhak lan relaksasi tetanggane.
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 kabeh sisik V-1 kaya; relaksasi luwih lanjut teges ana siklus negatif.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Bobot | ora negatif | apa wae (kalebu negatif) |
| Wektu | O((V+E) log V) | O(V·E) |
| Siklus neg. | ora ana | ndeteksi |
Gunakne Dijkstra kanthi standar kanggo bobot ora negatif (peta, jaringan). Gunakne Bellman-Ford nalika sisik negatif ana (ex, arbitrase). Dijkstra gagal karo senyep ing bobot negatif — a perangkap klasik.
Algoritma dalan paling cepet nggerakne ruting, navigasi, protokol jaringan, lan analisis biaya ketergantungan.
Ngerti watesan bobot ora negatif ing Dijkstra nyegah jawaban sing salah ing lapangan.
Ide relaksasi nghubungi pikiran greedy lan DP, dadi topik makmur tingkat senior.