9. óra
Gráfalgoritmusok 2. rész. Ha csak egy pontból egy másik pontba keressük a legrövidebb utat, akkor nem érdemes a Floyd-Warshall $n^3$-ös algoritmusát használni.
A jobb megoldás:
Dijkstra algoritmusa
Egy nemnegatív élsúlyozott (irányított) gráfban meghatározzuk a legrövidebb út hosszát, egy A csúcsból az összes többi csúcsba. A távolságokat és a legrövidebb utakat is előállítjuk. Érdekesség, hogy ha A-ból B-be keressük a legrövidebb utat, azt se lehet "olcsóbban" megcsinálni, minthogy A-ból az összes többi csúcsba megkeressük a legrövidebb utat.
Algoritmus
Ciklus minden v csúcsra:
d[v] := végtelen
elozo[v] := nemdefiniált
Ciklus vége
d[start] := 0; SOR := csúcsok halmaza
Ciklus amíg nem üres( SOR )
u := kivesz_min( SOR )
Ciklus az u csúcs v szomszédaira, amik még a SOR-ban vannak
dd := d[u] + súly(u, v)
Ha dd < d[v] akkor
d[v] := dd
elozo[v] := u
Elágazás vége
Ciklus vége
Ciklus vége
Példa
Feladat
