2012.03.26.Átismételjük Dijkstra algoritmusát, amivel nemnegatív élsúlyozott gráfban meghatározható egy csúcsból a többihez vezető legrövidebb út. Az algoritmus egy prioritási sor adatszerkezetet használ, a hatékonyság nagyban függ a prioritási sor megvalósításától. Az egyik lehetséges választás a kupac adatszerkezet, amivel gyors prioritási sor alkotható.
KupacA kupac egy majdnem teljes bináris fa, amelynek csúcsai tárolják a tömb elemeit. A kupac egy csomópontjában lévő érték mindig nagyobb (nem kisebb), mint a két gyermekcsomópont értéke. (Természetesen olyan kupac is van, ahol mindig a kisebb elem van feljebb.)
Dijkstra-algoritmus
Feladat
|