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).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
La BFS pe un graf fără costuri e corect să marchezi nodul ca vizitat când îl pui în coadă: prima dată când îl descoperi e și pe cel mai scurt drum. La Dijkstra, muchiile au costuri diferite, iar un drum cu mai multe muchii ieftine poate fi mai scurt decât o muchie scumpă găsită primul.
Dacă marchezi nodul vizitat la heappush, distanța găsită primul rămâne definitivă, chiar dacă mai târziu apare un drum mai bun. Exemplu: A → B costă 10, A → C costă 1, C → B costă 2. Codul greșit fixează B la 10 imediat, deși drumul prin C costă 3.
Varianta corectă: un nod devine definitiv abia când e scos din heap cu cea mai mică distanță. Până atunci, distanța lui se poate micșora; în heap pot rămâne intrări vechi, pe care le sari.
De ce apare: cauzele frecvente
1Vizitat la introducerea în heap
for v, cost in graf[u]:
if v not in vizitat:
vizitat.add(v)
dist[v] = d + cost
heapq.heappush(heap, (dist[v], v))for v, cost in graf[u]:
nd = d + cost
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))Distanța se actualizează de fiecare dată când găsești un drum mai scurt.
2Intrările vechi din heap nu sunt sărite
d, u = heapq.heappop(heap)
for v, cost in graf[u]:
...d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, cost in graf[u]:
...Fără verificare, rezultatul rămâne corect, dar nodurile se procesează de mai multe ori și algoritmul devine mai lent.
Repară eroarea, direct în pagină
Funcția dijkstra(graf, start) calculează costul minim de la start la fiecare oraș. Testul cu assert pică: spre B iese 10, deși drumul prin C costă 3. Repar-o ca testul să treacă și să afișeze {'A': 0, 'B': 3, 'C': 1, 'D': 4}.
import heapq
def dijkstra(graf, start):
dist = {start: 0}
vizitat = {start}
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
for v, cost in graf[u]:
if v not in vizitat:
vizitat.add(v)
dist[v] = d + cost
heapq.heappush(heap, (dist[v], v))
return dict(sorted(dist.items()))
graf = {'A': [('B', 10), ('C', 1)], 'B': [('D', 1)], 'C': [('B', 2)], 'D': []}
rez = dijkstra(graf, 'A')
assert rez == {'A': 0, 'B': 3, 'C': 1, 'D': 4}, f'distante gresite: {rez}'
print(rez){'A': 0, 'B': 3, 'C': 1, 'D': 4}Indiciu
Nu folosi vizitat: actualizează distanța când găsești una mai mică și sari peste intrările scoase cu d > dist[u].
Reparația
import heapq
def dijkstra(graf, start):
dist = {start: 0}
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, cost in graf[u]:
nd = d + cost
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dict(sorted(dist.items()))
graf = {'A': [('B', 10), ('C', 1)], 'B': [('D', 1)], 'C': [('B', 2)], 'D': []}
rez = dijkstra(graf, 'A')
assert rez == {'A': 0, 'B': 3, 'C': 1, 'D': 4}, f'distante gresite: {rez}'
print(rez)De ce merge
Din A, codul vechi descoperea B cu costul 10 și îl marca imediat vizitat. Când procesa C și găsea drumul A → C → B de cost 3, B era deja „închis”, iar eroarea se propaga și la D. Acum distanța lui B scade la 3, intrarea nouă (3, 'B') iese din heap înaintea celei vechi (10, 'B'), iar cea veche e sărită de if d > dist[u].
Cum o eviți pe viitor
Ține minte diferența: BFS marchează la introducere, Dijkstra fixează la extragere. Scrie Dijkstra mereu cu același șablon: dist inițializat cu start = 0, heap cu (0, start), la extragere if d > dist[u]: continue, la relaxare if nd < dist[v]. Testează pe un triunghi în care drumul cu două muchii e mai ieftin decât muchia directă.
Întrebări frecvente
Merge Dijkstra cu costuri negative?
Nu. Cu muchii negative, un nod scos din heap poate primi mai târziu o distanță mai mică. Pentru costuri negative folosește Bellman-Ford.
Ce complexitate are varianta cu intrări vechi în heap?
O((V + E) log V). Heap-ul poate avea până la E intrări, dar log E e de același ordin cu log V.
Erori înrudite
heapq scoate cel mai mic element, nu cel mai mare (max-heap lipsă) heapq din Python e un min-heap: heappop returnează mereu cel mai mic element. Pentru cel mai mare, pune valorile negate (heappush(h, -x), apoi -heappop(h)), folosește heapq.nlargest, sau, din Python 3.14, heappush_max / heappop_max. 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.
