Najkrótsze ścieżki uniemożliwiające każdą krawędź

Byłbym wdzięczny za wszelkie wskazówki lub warunki, które mogłyby doprowadzić mnie do właściwego kierunku.

Mamy ukierunkowany wykres $G=(V,E)$ i długości $l_{ij}$ dla każdej krawędzi $ij$które można uznać za pozytywne. Istnieje specjalny węzeł początkowy$s$ i węzeł końcowy $t$.

Dla każdej krawędzi $ij$, chcielibyśmy obliczyć długość najkrótszej ścieżki $s$ do $t$ który nie używa krawędzi $ij$.

Prostym algorytmem brutalnej siły jest uruchomienie algorytmu najkrótszej ścieżki dla każdej krawędzi, za każdym razem usuwając inną krawędź z oryginalnego wykresu. Czy istnieje bardziej wydajny algorytm, który wykorzystuje fakt, że w tym algorytmie brutalnej siły dzieje się wiele powtarzanych obliczeń?

Z góry dziękuję.

Wspomniany problem nazywa się „ścieżkami wymiany”. Oto kilka referencji:

1. Gotthilf i Lewenstein, Udoskonalone algorytmy dla k najprostszych najkrótszych ścieżek i problemów ze ścieżkami zastępczymi. Inf. Proc. Letters, 109 (7): 352–355, 2009. Artykuł ten przedstawia najszybszy jak dotąd dokładny algorytm dla problemu ścieżek wymiany, działający w czasie$O(mn+n^2\log\log n)$ czas na wykresach z $n$ węzły i $m$ krawędzie
2. A. Bernstein. Prawie optymalny algorytm do aproksymacji ścieżek zastępczych i k najkrótszych prostych ścieżek na ogólnych wykresach. W Proc. SODA, strony 742–755, 2010. Ten dokument niesamowicie podaje quasilinearny schemat przybliżenia czasu dla problemu.
3. J. Hershberger, S. Suri i A. Bhosle. Na trudności niektórych najkrótszych problemów ze ścieżką. W Proc. STACS, strony 343–354, 2003. Niniejszy artykuł pokazuje, że każdy algorytm porównywania ścieżek rozwiązujący problem zamiany ścieżek musi zająć co najmniej$\Omega(m\sqrt{n})$ czas.
4. V.Vassilevska W., R. Williams. Podkubicowe równoważności problemów ścieżki, macierzy i trójkąta. W Proc. FOCS, strony 645-654, 2010. Pokazujemy, że jeśli otrzymasz$O(n^{3-\varepsilon})$ algorytm dokładnego czasu dla ścieżek zastępczych dla dowolnej stałej $\varepsilon>0$, można to przekonwertować na $O(n^{3-\varepsilon'})$ algorytm czasowy dla wszystkich par najkrótszych ścieżek dla stałej $\varepsilon'>0$. Taki naprawdę subububiczny algorytm dla wszystkich par najkrótszych ścieżek jest od dawna otwartym problemem.
5. O. Weimann, R. Yuster. Ścieżki zastępcze poprzez szybkie mnożenie macierzy. W Proc. FOCS, strony 655-662, 2010. i V. Vassilevska W. Szybsze ścieżki wymiany. W Proc. SODA, strony 1337-1346, 2011. W tych dokumentach pokazano, jak korzystać z szybkiego mnożenia macierzy, aby znaleźć ścieżki zastępcze na wykresach z wagami całkowitych krawędzi w przedziale$\{-M,\ldots, M\}$. Ten ostatni artykuł podaje najbardziej znany do tej pory środowisko uruchomieniowe,$\tilde{O}(Mn^\omega)$.

Jeśli chcesz skojarzyć z każdą krawędzią długość najkrótszej ścieżki między $s$ i $t$, możesz rozpocząć od obliczenia najkrótszej ścieżki na całym wykresie i powiązać ją z każdą krawędzią, a nie z najkrótszą ścieżką, którą właśnie obliczyłeś długość bieżącej najkrótszej ścieżki. Potem masz co najwyżej$n-1$ pozostawione krawędzie, na które nie znasz odpowiedzi.