Algoritmul lui Dijkstra
O firmă de curierat are depozite în mai multe orașe și vrea timpul minim de livrare de la depozitul din Arad către fiecare oraș. Drumurile au durate diferite, deci BFS (care numără muchii) nu mai ajunge. Algoritmul lui Dijkstra găsește drumurile minime când costurile sunt pozitive, folosind un heap ca să extindă mereu cel mai apropiat oraș.
De ce nu BFS?
BFS a ajuns în C prima dată pe muchia directă (10 minute) și nu mai revine, deși drumul prin B durează 3 minute. BFS este corect doar când toate muchiile costă la fel.
from collections import deque
# A -> C direct: 1 muchie, dar 10 minute. A -> B -> C: 2 muchii, dar 3 minute.
graf = {'A': [('C', 10), ('B', 1)], 'B': [('C', 2)], 'C': []}
distanta = {'A': 0} 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…
- Heap-ul conține perechi (distanță, oraș); scoți cu heappop și ignori intrările vechi.
- Când găsești o distanță mai bună: actualizezi distanta, parinte și faci heappush.
- drum: urci prin parinte până la None și inversezi.
- Primele rânduri: Arad: 0 min, Cluj: 270 min, Deva: 140 min, Oradea: 120 min, Timișoara: 50 min.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan