Aproksimacijski algoritmi za iskanje vseh najkrajših poti v dinamičnih grafih

Topolovec, Jan (avtor), Fürst, Luka (mentor)

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

• Jezik: Slovenski jezik
• Ključne besede: dinamični grafi, dekrementalni model, aproksimacija najkrajših poti, emulator razdalj, monotono ES-drevo, vzporedni algoritmi
• Vrsta gradiva: Magistrsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2026
• PID: 20.500.12556/RUL-187849
• Datum objave v RUL: 15.09.2026

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Approximation algorithms for finding all shortest paths in dynamic graphs

Izvleček

This thesis addresses the decremental All-Pairs Shortest Paths (APSP) problem in dynamic graphs, where edges are only removed over time. Since static algorithms require a full recomputation after each change, they are inefficient for dynamic networks. Approximation approaches resolve this by trading exactness for significantly faster maintenance of distances. We implemented and compared four algorithms: the exact ES-tree algorithm, Krinninger's randomized and deterministic algorithms, and Dory's algorithm. We tested the algorithms on synthetic graphs (Erdős-Rényi, Barabási-Albert, tree-like, and regular) and compared them with respect to construction time, memory usage, and approximation accuracy. The ES-tree algorithm returns exact distances but is the most resource-intensive. Krinninger's randomized algorithm is fastest on sparse graphs, but its distance emulator exceeds the original graph size on dense graphs. Krinninger's deterministic algorithm is the most robust, achieving higher accuracy across all graph types. Dory's algorithm is memory-efficient for graphs with small diameter, but requires the diameter to be known in advance and returns infinite distance for pairs outside the specified depth. We further optimized Krinninger's deterministic algorithm. Checking distances up to 2 yielded the largest accuracy improvement. Incremental greedy center selection and a center dictionary together sped up construction by ~30 %, deletion by ~80 %, and queries by ~40 %. Parallel construction with 4 processes adds another 40-55 % speed up for n = 2000. An experiment in which we deleted up to 50 % of edges confirmed that the algorithm maintains its approximation guarantee across all test scenarios.

• Ključne besede: dynamic graphs, decremental model, shortest path approximation, distance emulator, monotone ES-tree, parallel algorithms