Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

22. óra

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ó.

Kupac

A 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