Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2013-2014‎ > ‎

20. alkalom

A legutóbb látott algoritmus hatékonysága erősen függ attól, hogy milyen gyorsan találjuk meg a még fel nem dolgozott csúcsok között azt, amelyiknek legkisebb a "távolságbecslése". A lineáris keresés nem elég jó, mert azzal N2-es algoritmust kapunk, ami egy 1000000 csúcsú gráfon már nem elég gyors.

A szokásos megoldás az, hogy a gráf csúcsait egy prioritási sorban tároljuk, amelynek kulcsa a gráf csúcsaihoz rendelt távolságbecslés.
Ez az egyszerűnek látszó megközelítés egy apró csapdát rejt: a programozási nyelvek által megvalósított prioritási sorok általában nem implementálják a "kulcs-csökkentés" műveletet.

Tehát ha a Dijkstra-algoritmus hatékony implementációját akarjuk megírni, szükségünk lehet arra, hogy "puszta kézzel" készítsünk el egy kupac adatszerkezeten alapuló prioritási sort. További "trükk", hogy az elemek eléréséhez szükségünk van a kupacbeli indexükre. Ez újra lineáris kereséshez vezethet, ha nem figyelünk. Mivel eleve ezt akarjuk elkerülni, inkább azt tehetjük, hogy karban tartunk egy tömböt, ami minden gráf csúcsra nyomon követi, hol van éppen a kupacban. Ez csak konstans sok új művelet, így még O(N log N) marad a legrövidebb utak algoritmus.

Feladatok

Dijkstra-algoritmus kupacon alapuló és a kulcs-csökkentést megengedő prioritási sorral
Gazdaságos tankolás (Visszavezethető az alapfeladatra.)