Her ikisi de ağırlıklı bir grafta bir kaynaktan en kısa yolları bulurlar. Dijkstra daha hızlıdır ancak negatif olmayan ağırlıklar gerektirir; Bellman-Ford daha yavaştır ancak negatif kenarları işler ve negatif döngüleri tespit eder.
En yakın ziyaret edilmemiş düğümü tekrar tekrar genişletir ve komşularını gevşetir.
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
Tüm kenarları V-1 kez gevşetin; daha fazla gevşetme negatif bir döngü anlamına gelir.
| | Dijkstra | Bellman-Ford | |---|---------|--------------|| | Ağırlıklar | negatif olmayan | herhangi (negatif dahil) | | Zaman | O((V+E) log V) | O(V·E) | | Neg. döngü | n/a | tespit eder |
Negatif olmayan ağırlıklar için Dijkstra'yı varsayılan olarak kullanın (haritalar, ağlar). Negatif kenarlar olduğunda Bellman-Ford kullanın (örn. arbitraj). Dijkstra negatif ağırlıklarda sessizce başarısız olur — klasik bir tuzak.
En kısa yol algoritmaları yönlendirme, navigasyon, ağ protokolleri ve bağımlılık maliyet analizi gücüdür.
Dijkstra'da negatif olmayan ağırlık kısıtlaması hakkındaki bilgi, sahada yanlış cevapları önler.
Gevşetme fikri açgözlü ve DP düşüncesini birbirine bağlar, bu da onu üst düzey bir zengin konu haline getirir.