Dijkstra dă distanțe greșite pe un graf cu muchii de cost negativ
Dijkstra presupune că toate costurile sunt pozitive sau zero: un nod scos din heap are deja distanța finală. Cu o muchie negativă, un drum mai lung poate deveni mai scurt după aceea. Pentru costuri negative folosește Bellman-Ford.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Dijkstra scoate mereu din heap nodul cu distanța cea mai mică și îl consideră finalizat. Asta e corect doar dacă orice muchie adăugată la un drum îl face mai lung sau la fel de lung, adică dacă toate costurile sunt mai mari sau egale cu zero.
Cu o muchie negativă, un nod finalizat devreme poate fi atins ulterior printr-un drum mai ieftin, care trece printr-un nod scos mai târziu. Unele implementări actualizează distanța, dar nu mai propagă îmbunătățirea mai departe, deci vecinii nodului rămân cu distanțe vechi. Altele intră în ciclu sau rulează mult mai mult. Nu apare nicio eroare.
Bellman-Ford relaxează toate muchiile de n - 1 ori și funcționează corect cu costuri negative, în O(n·m). O a n-a trecere care încă îmbunătățește ceva înseamnă că graful are un ciclu de cost negativ, iar distanța minimă nu există.
De ce apare: cauzele frecvente
1Dijkstra pe un graf cu costuri negative
graf = {'A': [('B', 2), ('C', 5)], 'C': [('B', -4)], 'B': [('D', 1)], 'D': []}
dist = dijkstra(graf, 'A')graf = {'A': [('B', 2), ('C', 5)], 'C': [('B', -4)], 'B': [('D', 1)], 'D': []}
dist = bellman_ford(graf, 'A')B e finalizat cu distanța 2 înainte să fie descoperit drumul A, C, B de cost 1, iar D rămâne cu distanța calculată din B vechi.
2Bellman-Ford, relaxare de n - 1 ori
for u in graf:
for v, cost in graf[u]:
if dist[u] + cost < dist[v]:
dist[v] = dist[u] + costfor _ in range(len(graf) - 1):
for u in graf:
for v, cost in graf[u]:
if dist[u] + cost < dist[v]:
dist[v] = dist[u] + costO singură trecere nu ajunge, pentru că depinde de ordinea muchiilor. După n - 1 treceri, orice drum minim (cu cel mult n - 1 muchii) a fost propagat complet.
Repară eroarea, direct în pagină
Funcția distante(graf, start) folosește Dijkstra pe un graf cu o muchie de cost negativ (C spre B, cost -4). Testul cu assert pică: distanța până la D iese 3 în loc de 2. Rescrie funcția cu Bellman-Ford ca să afișeze {'A': 0, 'B': 1, 'C': 5, 'D': 2}.
import heapq
def distante(graf, start):
dist = {nod: float('inf') for nod in graf}
dist[start] = 0
vizitat = set()
heap = [(0, start)]
while heap:
d, nod = heapq.heappop(heap)
if nod in vizitat:
continue
vizitat.add(nod)
for vecin, cost in graf[nod]:
if d + cost < dist[vecin]:
dist[vecin] = d + cost
heapq.heappush(heap, (dist[vecin], vecin))
return dist
graf = {'A': [('B', 2), ('C', 5)], 'B': [('D', 1)], 'C': [('B', -4)], 'D': []}
dist = distante(graf, 'A')
assert dist['D'] == 2, f'distante gresite: {dist}'
print(dist){'A': 0, 'B': 1, 'C': 5, 'D': 2}Indiciu
Relaxează toate muchiile de len(graf) - 1 ori, fără heap și fără noduri vizitate.
Reparația
def distante(graf, start):
dist = {nod: float('inf') for nod in graf}
dist[start] = 0
for _ in range(len(graf) - 1):
for u in graf:
for v, cost in graf[u]:
if dist[u] + cost < dist[v]:
dist[v] = dist[u] + cost
return dist
graf = {'A': [('B', 2), ('C', 5)], 'B': [('D', 1)], 'C': [('B', -4)], 'D': []}
dist = distante(graf, 'A')
assert dist['D'] == 2, f'distante gresite: {dist}'
print(dist)De ce merge
Dijkstra a scos B din heap cu distanța 2 și l-a marcat vizitat, apoi a calculat D = 3. Abia după aceea a scos C (distanța 5) și a găsit drumul spre B de cost 1, dar B era deja vizitat, deci D n-a mai fost actualizat. Bellman-Ford nu finalizează niciun nod: repetă relaxarea tuturor muchiilor de n - 1 = 3 ori, așa că îmbunătățirea lui B se propagă la D, care devine 2.
Cum o eviți pe viitor
Înainte să alegi algoritmul de drum minim, verifică costurile: toate egale cu 1 înseamnă BFS, costuri pozitive sau zero înseamnă Dijkstra, costuri negative înseamnă Bellman-Ford (sau 0-1 BFS pentru costuri 0 și 1). Pune un assert all(c >= 0 for ...) la începutul unei funcții Dijkstra, ca să afli imediat dacă datele nu respectă condiția.
Întrebări frecvente
Nu merge dacă adun o constantă la toate costurile, ca să devină pozitive?
Nu. Un drum cu mai multe muchii primește constanta de mai multe ori, deci drumurile cu puține muchii sunt favorizate, iar drumul minim se schimbă.
Ce e un ciclu de cost negativ?
Un ciclu ale cărui costuri însumate sunt sub zero. Parcurgându-l de mai multe ori, costul scade la nesfârșit, deci distanța minimă nu există. Bellman-Ford îl detectează cu o trecere în plus.
Erori înrudite
Dijkstra dă distanțe greșite: nodul e marcat vizitat când e pus în heap La Dijkstra, prima distanță găsită spre un nod nu e neapărat cea mai mică. Dacă marchezi nodul ca vizitat când îl pui în heap, nu mai poți îmbunătăți distanța lui. Actualizează distanța ori de câte ori găsești una mai mică și ignoră la scoatere intrările vechi (if d > dist[u]: continue). BFS cu coada.pop() în loc de popleft(): distanțele ies prea mari pop() scoate ultimul element, deci coada ta funcționează ca o stivă și parcurgerea devine DFS. Nodurile sunt descoperite pe drumuri lungi și primesc distanțe prea mari. La BFS folosește deque și scoate cu popleft() (cel mai vechi element). OverflowError: cannot convert float infinity to integer Încerci să transformi float('inf') într-un întreg, de obicei cu int() sau round() pe o distanță care a rămas infinită pentru că nodul nu poate fi atins. Verifică înainte dacă valoarea e infinită (math.isinf sau == float('inf')) și returnează -1 sau un mesaj. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
