Entrambi trovano i percorsi più brevi da una sorgente in un grafo pesato. Dijkstra è più veloce ma richiede pesi non-negativi; Bellman-Ford è più lento ma gestisce spigoli negativi e rileva cicli negativi.
Ripetutamente espandi il nodo non visitato più vicino e rilassa i suoi vicini.
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
Rilassa tutti gli spigoli V-1 volte; un ulteriore rilassamento indica un ciclo negativo.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Pesi | non-negativi | qualsiasi (inclusi negativi) |
| Tempo | O((V+E) log V) | O(V·E) |
| Ciclo neg. | n/a | lo rileva |
Usa Dijkstra per default con pesi non-negativi (mappe, reti). Usa Bellman-Ford quando esistono spigoli negativi (ad es., arbitraggio). Dijkstra fallisce silenziosamente con pesi negativi — una trappola classica.
Gli algoritmi di percorso più breve alimentano il routing, la navigazione, i protocolli di rete e l'analisi dei costi delle dipendenze.
Conoscere il vincolo di pesi non-negativi su Dijkstra previene risposte sbagliate in pratica.
L'idea di rilassamento collega il pensiero greedy e DP, rendendola un argomento ricco di livello senior.