...
Eroare Algoritmi și structuri de date · Grafuri: BFS și DFS

Dijkstra dă distanțe greșite: nodul e marcat vizitat când e pus în heap

Pe scurt

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

Greșit
PYTHON
for v, cost in graf[u]:
    if v not in vizitat:
        vizitat.add(v)
        dist[v] = d + cost
        heapq.heappush(heap, (dist[v], v))
Corect
PYTHON
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

Greșit
PYTHON
d, u = heapq.heappop(heap)
for v, cost in graf[u]:
    ...
Corect
PYTHON
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ă tu

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}.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
{'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].

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.