Aproksimacijski algoritmi za iskanje vseh najkrajših poti v dinamičnih grafihTopolovec, Jan (Avtor) Fürst, Luka (Mentor) dinamični grafidekrementalni modelaproksimacija najkrajših potiemulator razdaljmonotono ES-drevovzporedni algoritmiV magistrski nalogi obravnavamo dekrementalni problem vseh najkrajših poti (APSP) v dinamičnih grafih, kjer se povezave zgolj odstranjujejo. Ker statični algoritmi ob vsaki spremembi zahtevajo ponovni izračun od začetka, so za dinamična omrežja neučinkoviti. Aproksimacijski pristopi to rešijo z zamenjavo eksaktnosti za bistveno večjo hitrost vzdrževanja razdalj. Implementirali in primerjali smo štiri algoritme: eksaktni ES-algoritem, Krinningerjev randomiziran in deterministični algoritem ter Doryjev algoritem. Algoritme smo preizkusili na sintetičnih grafih (Erdős-Rényi, Barabási-Albert, drevesasti in regularni) in jih primerjali glede na čas gradnje, porabo pomnilnika in natančnost. ES-algoritem vrača eksaktne razdalje, a je najpotratnejši. Krinningerjev randomizirani algoritem je pri redkih grafih najhitrejši, pri gostih pa emulator razdalj preseže velikost originalnega grafa. Krinningerjev deterministični algoritem je najbolj robusten in dosega višjo natančnost na vseh tipih grafov. Doryjev algoritem je pomnilniško učinkovit za grafe z majhnim premerom, a zahteva vnaprej znan premer in za pare zunaj podane globine vrača neskončno razdaljo. Krinningerjev deterministični algoritem smo dodatno optimizirali. Preverjanje do razdalje 2 je prineslo največji skok pri natančnosti. Inkrementalni požrešni izbor centrov in slovar centrov sta pohitrila gradnjo za ~30 %, brisanje za ~80 % in poizvedbe za ~40 %. Vzporedna gradnja s 4 procesi doda še 40-55 % pohitritve gradnje pri n = 2000. Eksperiment z odstranitvijo do 50 % povezav je potrdil, da algoritem ohranja aproksimacijsko zagotovilo v vseh testnih scenarijih.20262026-09-15 10:20:04Magistrsko delo/naloga187849sl