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

Dijkstra dă distanțe greșite pe un graf cu muchii de cost negativ

Pe scurt

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

Greșit
PYTHON
graf = {'A': [('B', 2), ('C', 5)], 'C': [('B', -4)], 'B': [('D', 1)], 'D': []}
dist = dijkstra(graf, 'A')
Corect
PYTHON
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

Greșit
PYTHON
for u in graf:
    for v, cost in graf[u]:
        if dist[u] + cost < dist[v]:
            dist[v] = dist[u] + cost
Corect
PYTHON
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

O 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ă tu

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

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

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

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