Leírás
Az "All Pairs Shortest Path" probléma célja, hogy megtalálja a legrövidebb
utakat bármely két csúcs között.
Az ilyen távolságokat egy távolság-mátrixban tároljuk.
A teljesen dinamikus verzióban arra törekszünk, hogy a távolság-mátrixot
dinamikusan tudjuk frissíteni minél gyorsabban egy olyan gráf esetében,
amiből folyamatosan törölhetünk és hozzáadhatunk csúcsokat (es a csúcsokhoz
tartozó éleket).
A teljesen dinamikus APSP problémára mutatunk egy új, egyszerű, a korábbi
megoldásoktól független, randomizált, tehát csak nagy valószínűséggel
működő algoritmust.
Az első algoritmus csak nem-negatív súlyokkal működik megbízhatóan (ahogy sok
más APSP algoritmus is), de látni fogjuk, hogy általánosíthatjuk konzervatív
súlyozásra is.
Elsőként bebizonyítjuk a futásidő-korlátot és a helyes
működést (a fent említett nagy
valószínűséggel), majd 3 lépésben általánosítjuk módszerünket:
- kiterjesztjük negatív súlyokra is;
- súlyozatlan gráfokra módosítjuk;
- determinisztikussá tesszük az algoritmust;
- majd megmutatjuk, hogy az algoritmusnak megadható egy olyan
egyszerű kiterjesztése, hogy visszaadja a legrövidebb utat is a
távolság-mátrix frissitése után.