Floyd-Warshall z ujemnymi cyklami. Jak znaleźć wszystkie niezdefiniowane ścieżki?

Question

Wdrożyłem algorytm Floyd Warshall i działa, ale problem polega na tym, że nie wiem, jak znaleźć wszystkie ścieżki, które nie są zdefiniowane. Szukałem w Internecie, ale mogę znaleźć tylko odpowiedzi, jak wykryć, czy wykres ma ujemne cykle, czy nie.

vector< vector <int> > floyd_warshall(vector< vector<int> > d, int n){ 
    for(int i = 0; i < n; i++) d[i][i] = 0; 

    for(int i = 0; i < n; i++){ 
     for(int j = 0; j < n; j++){ 
      for(int k = 0; k < n; k++){ 
       if(d[j][i] + d[i][k] < d[j][k] and d[j][i] != INF and d[i][k] != INF){ 
        d[j][k] = d[j][i] + d[i][k]; 
       } 
      } 
     } 
    } 

    return d; 
} 

Po uruchomieniu algorytmu na wykresie:

from: to: weight: 
0  1  1 
1  2  -1 
2  1  -1 
1  3  1 
4  0  1 

uzyskać macierz sąsiedztwa:

| 0  1  2  3  4 
--|---------------------------- 
0 | 0 -1 -2 -2  INF 
1 | INF -2 -3 -3  INF 
2 | INF -3 -4 -4  INF 
3 | INF INF INF 0  INF 
4 | 1 -2 -3 -7  0 

wiem, że jeśli węzeł i jest częścią negatywnej cyklu Ma wartość ujemna w pozycji d [i] [i] w macierzy. Jeśli więc sprawdzę przekątną macierzy, mogę znaleźć wszystkie węzły, które są częścią ujemnego cyklu. Jeśli spojrzymy w powyższy przykład, widzimy, że węzły 1 i 2 są częścią cyklu ujemnego. Chodzi o to, że chcę znaleźć, które ścieżki są zdefiniowane i które nie są zdefiniowane. Jeśli możesz przejść od A do B przez ujemny cykl, długość ścieżki powinna być nieokreślona, ​​ponieważ może być dowolnie mała.

Pytanie brzmi: jak mogę znaleźć wszystkie niezdefiniowane ścieżki?

że chce algorytm powróci macierz: (zamiast tego, wyżej)

| 0  1  2  3  4 
--|---------------------------- 
0 | 0 -INF -INF -INF INF 
1 | INF -INF -INF -INF INF 
2 | INF -INF -INF -INF INF 
3 | INF INF INF  0 INF 
4 | 1 -INF -INF -INF 0 

gdzie D [i] [j] = INF oznacza, że ​​nie ma ścieżki między I i J, oraz - INF oznacza, że ​​istnieje arbitralna mała ścieżka między i i j (ścieżka przechodzi gdzieś ujemną pętlę), a poza tym d [i] [j] jest najkrótszą długością między i i j.

Myślałem o testowaniu każdej ścieżki, ale to byłoby zbyt wolne. Musi istnieć jakiś standardowy sposób rozwiązania tego problemu, prawda?

Dziękuję

Answer 1

Cóż, znalazłem rozwiązanie mojego własnego problemu.

for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) // Go through all possible sources and targets 

     for(int k = 0; d[i][j] != -INF && k < n; k++) 
      if(d[i][k] != INF && // Is there any path from i to k? 
       d[k][j] != INF && // Is there any path from k to j? 
       d[k][k] < 0)  // Is k part of a negative loop? 

       d[i][j] = -INF; // If all the above are true 
            // then the path from i to k is undefined 

Myślę, że to powinno działać i wydaje się działać również.

Answer 2

Algorytm Floyd-Warshall podaje poprawny wynik, o ile na wykresie wejściowym nie ma żadnych ujemnych cykli. W przypadku, gdy istnieje cykl ujemny, obliczanie najkrótszej (prostej) ścieżki jest problemem NP-trudnym, a algorytm Floyd-Warshall nie wyprowadza poprawnego wyniku.

Ale można wykryć obecność ujemnego cyklu, sprawdzając, czy w przekątnej matrycy znajduje się ujemny wpis. Można to zrobić w linii 8 i przewodem 9 tego algorytmu:

1. M[i, j] := ∞ ∀i 6= j 
2. M[i, i] := 0 ∀i 
3. M[i, j] := c((i, j)) ∀(i, j) ∈ E(G) 

4. for i := 1 to n do 
5. for j := 1 to n do 
6.  for k := 1 to n do 
7.  if M[j, k] > M[j, i] + M[i, k] 
      then M[j, k] := M[j, i] + M[i, k] 

8. for i := 1 to n do 
9. if M[i, i] < 0 then return(’graph contains a negative cycle’) 

Source

Answer 3

Algorytm Floyda-Warshalla jest stosowany, aby znaleźć najkrótszej ścieżki pomiędzy wszystkimi parami węzłów ważoną wykresie dodatni lub ujemny ciężary krawędzi.

Następujący algorytm akceptuje macierz sąsiedztwa, w której Double.POSITIVE_INFINITY jest używany do wskazania, że ​​dwa węzły nie łączą się. Dla każdego węzła również prawdopodobnie będziesz chciał zainicjować wagę 0 dla siebie.

Ta metoda aktualizuje początkową macierz, aby wskazać minimalną odległość między wszystkimi parami węzłów. Jeśli najkrótsza ścieżka jest dowolnie mała, odpowiedź jest zapisywana jako Double.NEGATIVE_INFINITY. Jeśli dwa węzły nie mogą się nawzajem połączyć, nadal jest to Double.POSITIVE_INFINITY. Ta implementacja uruchamia dwukrotnie Floyd Warshall i jeśli długość ścieżki jest mniejsza niż poprzednio, jesteśmy w cyklu ujemnym.

static void floydWarshall(double[][] dist) { 

    int n = dist.length; 

    // Compute shortest paths 
    for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
     if (dist[i][k] + dist[k][j] < dist[i][j]) 
      dist[i][j] = dist[i][k] + dist[k][j]; 

    // Identify negative cycles 
    for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
     if (dist[i][k] + dist[k][j] < dist[i][j]) 
      dist[i][j] = Double.NEGATIVE_INFINITY; 

}