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

9

Chcę produkować k najkrótsza droga (kbył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 knajkrótsza ścieżka trasy do każdej pary; Teraz szukam bardziej wydajnej alternatywy (prawdopodobnie z programowaniem dynamicznym).

algorithms graphs optimization shortest-path Franklin Yu
źródło
3
Szczerze mówiąc, na 100 wierzchołków wydaje się mało prawdopodobne, że potrzebujesz czegoś bardziej wydajnego niż rozwiązanie każdego z 45 000 problemów parami.
David Richerby,

Odpowiedzi:

6

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 kproblem 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 kProste 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.

Kłamstwo
źródło
Dziękuję Ci. Ponieważ pracuję z mapą metra, potrzebuję, aby były prostą ścieżką (moje oprogramowanie nie ma sensu prowadzić ludzi tam iz powrotem), więc sądzę, że wybrałbym algorytm Yana .
Franklin Yu,
Interesujące i dość zaskakujące, że najwyraźniej 10 000 przypadków problemu nie da się rozwiązać szybciej niż rozwiązanie 10 000 pojedynczych przypadków, jedna po drugiej.
gnasher729,
idea ścieżek z pętlami zawartymi w „najkrótszych ścieżkach” wydaje się sprzeczna z intuicją i niezwykła, ponieważ wydaje się, że istnieje równoważna „ścieżka” z usuniętą pętlą, i zastanawia się również, czy można je skutecznie skonstruować z prostych ścieżek itp.
od