Ambii găsesc cele mai scurte căi de la o sursă într-un graf ponderat. Dijkstra este mai rapid, dar necesită greutăți non-negative; Bellman-Ford este mai lent, dar gestionează muchii negative și detectează cicluri negative.
Extinde în mod repetat nodul nevisitat cel mai apropiat și relaxează vecinii acestuia.
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
Relaxează toate muchiile V-1 ori; relaxare suplimentară înseamnă un ciclu negativ.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Greutăți | non-negative | orice (inclusiv negative) |
| Timp | O((V+E) log V) | O(V·E) |
| Ciclu neg. | n/a | îl detectează |
Foloseşte Dijkstra implicit pentru greutăți non-negative (hărți, rețele). Foloseşte Bellman-Ford când există muchii negative (de ex. arbitraj). Dijkstra se defectează în tăcere pe greutăți negative — o capcană clasică.
Algoritmii de cale cea mai scurtă alimentează rutare, navigație, protocoale de rețea și analiza costului dependențelor.
A cunoaște constrângerea greutății non-negative pe Dijkstra previne răspunsuri greșite în practică.
Ideea de relaxare conectează gândirea greedy și DP, făcând-o un subiect bogat la nivel senior.
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează