Czy potrafimy znaleźć k najkrótszych ścieżek między wszystkimi parami szybciej niż wielokrotne rozwiązywanie problemu parami?

Chcę produkować $k$ najkrótsza droga ($k$byłoby mniej niż 10) między wszystkimi parami na wykresie. Wykres to (właściwie mapa metra):

• dodatnio ważony
• bezkierunkowy
• rzadki
• z około 100 węzłami

Mój obecny plan ma zastosowanie $k$najkrótsza ścieżka trasy do każdej pary; Teraz szukam bardziej wydajnej alternatywy (prawdopodobnie z programowaniem dynamicznym).

Przede wszystkim zasadnicza różnica w informatyce $k$- najkrótsze ścieżki to, czy ścieżki muszą być proste, czy nie. Ścieżka nazywa się prosta , jeśli nie zawiera wielokrotnie węzłów. Na przykład ścieżka z pętlą nie jest prosta. Pamiętaj, że na stronie w Wikipedii, do której linkujesz, artykuły dotyczą niekoniecznie prostych ścieżek. Przypadek prostych ścieżek wydaje się trudniejszy niż przypadek niekoniecznie prostych ścieżek.

Wszystkie pary $k$-najkrótszy problem prostych ścieżek

Wydaje się, że jest to dość młody obszar badań. Ostatni artykuł Agarwal i Ramachandran można znaleźć na ArXiv [1]. Sekcja poprzedniej pracy da ci również wgląd w historię problemu.

Wszystkie pary $k$problem najkrótszych ścieżek

Tutaj rzeczywiście najlepszym wyborem jest wielokrotne stosowanie algorytmu Eppsteinsa [2]. Ogólne spostrzeżenie, że wielokrotne stosowanie algorytmu dla wersji z jednym źródłem problemu jest najszybszym podejściem, zostało przeprowadzone już w 1977 r. Przez EL Lawlera [3]; Eppstein zapewnia najszybszy jak dotąd algorytm dla tego podproblemu.

Bibliografia

[1] Agarwal, U. i Ramachandran, V. Finding $k$Proste najkrótsze ścieżki i cykle. arXiv: 1512.02157 [cs.DS] https://arxiv.org/pdf/1512.02157.pdf

[2] Eppstein, D. Znalezienie k najkrótszych ścieżek. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, EL Komentarz do obliczenia k najkrótszych ścieżek na wykresie. Communications of the ACM, 20 (8): 603–605, 1977.