...
Algoritmi pe grafuri

Algoritmul lui Dijkstra, explicat pas cu pas

Pe scurt

Algoritmul lui Dijkstra găsește drumurile cele mai ieftine dintr-un nod spre toate celelalte noduri ale unui graf în care muchiile au costuri pozitive (distanțe, timpi, prețuri). La fiecare pas fixează nodul nevizitat la care se ajunge cel mai ieftin și verifică dacă prin el se poate ajunge mai ieftin la vecini. E algoritmul din spatele navigației GPS și al rutării în rețele.

  • O((n + m) log n)cu coadă de priorități
  • ≥ 0costurile muchiilor trebuie să fie pozitive
  • 1nod sursă, drumuri spre toate celelalte
  • 2lecții gratuite, fără card
DIJKSTRA · DRUM MINIM 4 2 1 5 8 2 6 3 ABCDEF cost 13 A → F

Algoritmul lui Dijkstra, în animație

Apasă „Pornește”. Numărul de lângă fiecare nod e costul cel mai mic găsit până acum; nodul galben e cel ales, iar cele verzi sunt fixate. La final se aprinde drumul minim spre nodul ales.

Cum funcționează algoritmul lui Dijkstra

  1. Pui dist[sursă] = 0 și dist = ∞ pentru toate celelalte noduri.
  2. Alegi nodul nefixat cu cel mai mic dist. Costul lui nu mai poate scădea, pentru că orice alt drum ar trece printr-un nod mai scump: îl fixezi.
  3. Pentru fiecare vecin al lui, verifici dacă drumul prin nodul fixat e mai ieftin: dacă dist[x] + cost(x, y) < dist[y], actualizezi dist[y] și ții minte că ai venit din x. Pasul se numește relaxare.
  4. Repeți până fixezi toate nodurile la care se poate ajunge.

În exemplul din animație, drumul direct A → B costă 4, dar A → C → B costă 2 + 1 = 3, iar Dijkstra îl găsește pe cel ieftin. Drumul minim A → F trece prin C, B, D și E și costă 13.

Algoritmul lui Dijkstra în C++, Python și Java

Varianta cu coadă de priorități (heap), cea folosită în practică și la interviuri.

import heapq

graf = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 1), ("D", 5)],
    "C": [("A", 2), ("B", 1), ("D", 8), ("E", 10)],
    "D": [("B", 5), ("C", 8), ("E", 2), ("F", 6)],
    "E": [("C", 10), ("D", 2), ("F", 3)],
    "F": [("D", 6), ("E", 3)],
}


def dijkstra(start):
    dist = {nod: float("inf") for nod in graf}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, nod = heapq.heappop(heap)
        if d > dist[nod]:
            continue                      # o intrare veche, deja îmbunătățită
        for vecin, cost in graf[nod]:
            if d + cost < dist[vecin]:
                dist[vecin] = d + cost
                heapq.heappush(heap, (dist[vecin], vecin))
    return dist


print(dijkstra("A"))   # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13}

Încearcă: drumul cel mai scurt între orașe

Problema din lecția 122 a cursului de algoritmi: Dijkstra cu heapq pe o hartă cu minute între orașe.

Exercițiu din lecția 122 · cursul de algoritmi

Algoritmul lui Dijkstra

Scrie dijkstra(graf, start), care returnează tuplul (distanta, parinte) (dicționare doar pentru nodurile accesibile), și drum(parinte, tinta), care returnează drumul de la start la țintă ca listă ([] dacă ținta nu e accesibilă). Graful are forma oras -> [(vecin, minute), ...].

  1. Heap-ul conține perechi (distanță, oraș); scoți cu heappop și ignori intrările vechi.
  2. Când găsești o distanță mai bună: actualizezi distanta, parinte și faci heappush.
  3. drum: urci prin parinte până la None și inversezi.
  4. Primele rânduri: Arad: 0 min, Cluj: 270 min, Deva: 140 min, Oradea: 120 min, Timișoara: 50 min.
Indiciu: Deva este la 140 de minute prin Timișoara (50 + 90), deși drumul direct din Arad are 150.
import heapq


def dijkstra(graf, start):
    distanta = {start: 0}
    parinte = {start: None}
    heap = [(0, start)]
    while heap:
        d, nod = heapq.heappop(heap)
        if d > distanta[nod]:
            continue
        for vecin, cost in graf[nod]:
            nou = d + cost
            if vecin not in distanta or nou < distanta[vecin]:
                distanta[vecin] = nou
                parinte[vecin] = nod
                heapq.heappush(heap, (nou, vecin))
    return distanta, parinte


def drum(parinte, tinta):
    if tinta not in parinte:
        return []
    rezultat = []
    nod = tinta
    while nod is not None:
        rezultat.append(nod)
        nod = parinte[nod]
    rezultat.reverse()
    return rezultat


harta = {
    'Arad': [('Timișoara', 50), ('Oradea', 120), ('Deva', 150)],
    'Timișoara': [('Arad', 50), ('Deva', 90)],
    'Oradea': [('Arad', 120), ('Cluj', 150)],
    'Deva': [('Arad', 150), ('Timișoara', 90), ('Cluj', 160)],
    'Cluj': [('Oradea', 150), ('Deva', 160)],
}

distanta, parinte = dijkstra(harta, 'Arad')
for oras in sorted(distanta):
    print(f'{oras}: {distanta[oras]} min')
print(drum(parinte, 'Cluj'))
print(drum(parinte, 'Deva'))

distanta, parinte = dijkstra(harta, 'Cluj')
print(distanta.get('Timișoara'), drum(parinte, 'Timișoara'))
print(drum(parinte, 'Iași'))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Complexitate și limite

ImplementareComplexitateCând o folosești
cu vector, caut minimul la fiecare pasO(n²)grafuri dese, n mic (varianta clasică de la BAC și olimpiadă)
cu coadă de priorități (heap)O((n + m) log n)grafuri rare, cazul obișnuit

Limita importantă: Dijkstra nu funcționează corect dacă există muchii cu cost negativ, pentru că un nod deja fixat ar putea deveni mai ieftin. Pentru costuri negative se folosește Bellman-Ford. Dacă toate muchiile au același cost, ajunge un BFS, mai simplu și mai rapid.

Unde se folosește

Navigația GPS (drumul cel mai scurt sau cel mai rapid), rutarea pachetelor în internet (protocolul OSPF), jocuri (deplasarea personajelor), planificarea zborurilor după preț. La interviuri apare ca „network delay time”, „cel mai ieftin zbor cu cel mult k escale” sau drumul minim pe o grilă cu costuri. Coada de priorități din spate e un heap, un arbore binar complet care ține mereu minimul în vârf; îl folosești în lecția despre heap.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

La cursul de Java am avut placerea sa acumulez o multitudine de informatii foarte utile pentru a imi incepe drumul de programator de la trainerul Gabriel, un trainer vizibil foarte pasionat de ceea ce face, rabdator cu elevii sai si dornic sa ne dezvolte pe partea profesionala. Astept cu nerabdare urmatorul curs!!

Fotografia lui Bea Danciu, cursant al Academiei ProgramatorilorBea DanciuRecenzie pe Google

Recomand cursul online de programare, foarte bine structurat, explicatiile sunt usor de inteles si contine foarte multe exercitii practice.

Fotografia lui Ioana Dumitrache, cursant al Academiei ProgramatorilorIoana DumitracheRecenzie pe Google

Am participat la cursul C# incepatori. Pentru mine a fost o experienta eficienta. Nu stiam nimic despre programare, insa, acest lucru nu a fost o problema. Structura cursului a fost pe intelesul oricui, iar Gabi a avut rabdarea sa explice pas cu pas. Si de mai muuulte ori cand era cazul :)

Fotografia lui Sorin, cursant al Academiei ProgramatorilorSorinRecenzie pe Google

Întrebări frecvente

Ce face algoritmul lui Dijkstra?

Găsește drumurile de cost minim de la un nod sursă la toate celelalte noduri dintr-un graf cu costuri nenegative pe muchii. Pe lângă cost, poate reține și drumul efectiv, prin nodul din care s-a ajuns în fiecare nod.

Ce complexitate are algoritmul lui Dijkstra?

O(n²) în varianta simplă, care caută minimul într-un vector la fiecare pas, și O((n + m) log n) cu o coadă de priorități (heap), unde n este numărul de noduri și m numărul de muchii.

De ce nu merge Dijkstra cu costuri negative?

Pentru că algoritmul fixează un nod pe baza presupunerii că niciun drum viitor nu poate fi mai ieftin. Cu o muchie negativă, un drum găsit mai târziu poate scădea costul unui nod deja fixat. Pentru astfel de grafuri se folosește algoritmul Bellman-Ford.

Care e diferența dintre Dijkstra și BFS?

BFS găsește drumul cu cel mai mic număr de muchii și merge când toate muchiile au același cost. Dijkstra ține cont de costuri diferite și folosește o coadă de priorități în loc de o coadă simplă.

Cine a inventat algoritmul?

Informaticianul olandez Edsger W. Dijkstra, în 1956, publicat în 1959. A spus că l-a gândit în aproximativ 20 de minute, pe terasa unei cafenele din Amsterdam.

Unde exersez algoritmul lui Dijkstra?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor, lecția „Algoritmul lui Dijkstra”, împreună cu lecțiile despre heap, BFS și DFS, cu probleme rezolvate în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.