Naslov diplomskega dela: Primerjava algoritmov za iskanje najcenejše poti v grafu

Povzetek:

Diplomska naloga obravnava primerjavo algoritmov za iskanje najcenejše poti v grafu. V delu je predstavljena primerjava teoretične časovne zahtevnosti algoritmov in njihove zmogljivosti pri praktični implementaciji.

Naloga je razdeljena na štiri vsebinske sklope. Najprej je podan pregled petih obravnavanih algoritmov – Dijkstrovega algoritma z dvojiško kopico, Dijkstrovega algoritma s Fibonaccijevo kopico, Bellman–Fordovega algoritma, Johnsonovega algoritma in Floyd–Warshallovega algoritma – skupaj z opisom njihovega delovanja in teoretično časovno zahtevnostjo. V drugem sklopu so opisane testne množice, ki se delijo na umetno generirane grafe in standardne grafe iz zbirke SNAP, ki predstavljajo realna omrežja. Tretji sklop opisuje testno okolje ALGator, v katerem so bili izvedeni vsi eksperimenti.

Četrti sklop predstavlja pregled in primerjavo rezultatov testiranja ter diskusijo ugotovitev.

Pri analizi rezultatov je poudarek na iskanju odstopanj od teoretično pričakovanih vrednosti in njihovi razlagi. Izpostavljeni sta dve glavni odstopanji. Prvo je obnašanje Dijkstrovega algoritma: implementacija z dvojiško kopico se v praksi izkaže za hitrejšo od implementacije s Fibonaccijevo kopico, Čeprav ima slednja boljšo teoretično časovno zahtevnost. Razlog so višji konstantni faktorji in slabša krajevna lokalnost podatkov v predpomnilniku pri Fibonaccijevi kopici. Drugo odstopanje smo opazili pri grafih z več kot milijon vozlišči in izjemno nizko gostoto, kjer Johnsonov algoritem preseže Bellman-Fordovega, čeprav ima slednji boljšo asimptotično zahtevnost.

Mentor: doc. dr. Tomaž Dobravec

Komisija za zagovor:

    - doc. dr. Boštjan Slivnik, predsednik

    - doc. dr. Luka Fürst, član

    - doc. dr. Tomaž Dobravec, mentor