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), ...].
- Heap-ul conține perechi
(distanță, oraș); scoți cuheappopși ignori intrările vechi. - Când găsești o distanță mai bună: actualizezi
distanta,parinteși faciheappush. drum: urci prinparintepână laNoneși inversezi.- Primele rânduri:
Arad: 0 min,Cluj: 270 min,Deva: 140 min,Oradea: 120 min,Timișoara: 50 min.
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'))


