Floyd-Warshall mit negativen Zyklen. Wie finde ich alle nicht definierten Pfade?

Question

Ich habe den Floyd Warshall-Algorithmus implementiert und es funktioniert, aber das Problem ist, dass ich nicht weiß, wie ich alle Pfade finden kann, die nicht definiert sind. Ich habe im Internet gesucht, aber ich kann nur Antworten finden, um festzustellen, ob ein Diagramm negative Zyklen hat oder nicht.

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; 
} 

Nach dem Algorithmus auf dem Graphen läuft:

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

Ich erhalte die Adjazenzmatrix:

| 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 

Ich weiß, dass, wenn der Knoten i Teil eines negativen Zyklus ist es eine hat negativer Wert an der Position d [i] [i] in der Matrix. Wenn ich also die Diagonale der Matrix überprüfe, kann ich alle Knoten finden, die Teil eines negativen Zyklus sind. Wenn wir uns das obige Beispiel ansehen, können wir sehen, dass Knoten 1 und 2 Teile eines negativen Zyklus sind. Die Sache ist, dass ich herausfinden möchte, welche Pfade definiert sind und welche nicht definiert sind. Wenn Sie von A nach B durch einen negativen Zyklus kommen können, sollte die Länge des Pfades undefiniert sein, da er beliebig klein sein kann.

Die Frage ist also, wie kann ich alle undefinierten Pfade finden?

Ich möchte den Algorithmus die Matrix zurückzukehren: (statt der oben)

| 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 

Wo d [i] [j] = INF bedeutet, dass es keinen Weg zwischen i und j, und - INF bedeutet, dass es einen beliebigen kleinen Pfad zwischen i und j gibt (der Pfad passiert irgendwo eine negative Schleife) und ansonsten ist d [i] [j] die kürzeste Länge zwischen i und j.

Ich dachte an jeden einzelnen Pfad zu testen, aber das wäre wahrscheinlich zu langsam. Es muss einen Standardweg geben, um dieses Problem zu lösen, oder?

Vielen Dank

Answer 1

Nun, ich habe eine Lösung für mein eigenes Problem gefunden.

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 

Ich denke, es sollte funktionieren und es scheint zu arbeiten.

Answer 2

Der Floyd-Warshall-Algorithmus gibt das korrekte Ergebnis aus, solange keine negativen Zyklen im Eingabediagramm vorhanden sind. Falls ein negativer Zyklus existiert, ist die Berechnung eines kürzesten (einfachen) Pfads ein NP-schweres Problem, und der Floyd-Warshall-Algorithmus gibt nicht das korrekte Ergebnis aus.

Es ist jedoch möglich, das Vorhandensein eines negativen Zyklus zu erkennen, indem überprüft wird, ob ein negativer Eintrag in der Diagonalen der Matrix vorhanden ist. Dies ist in der Leitung 8 und die Leitung 9 dieses Algorithmus durchgeführt:

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

Der Floyd-Warshall-Algorithmus verwendet, um die kürzesten Pfade zwischen allen Paaren von Knoten in einem gewichteten Graphen mit positiven oder negativen zu finden Kantengewichte.

Der folgende Algorithmus akzeptiert eine Adjazenzmatrix, wobei Double.POSITIVE_INFINITY verwendet wird, um anzuzeigen, dass zwei Knoten keine Verbindung herstellen. Für jeden Knoten möchten Sie wahrscheinlich auch eine Gewichtung von 0 initialisieren.

Diese Methode aktualisiert die anfängliche Matrix, um den Mindestabstand zwischen allen Knotenpaaren anzugeben. Wenn der kürzeste Pfad beliebig klein ist, wird die Antwort als Double.NEGATIVE_INFINITY gespeichert. Wenn zwei Knoten einander nicht erreichen können, ist es immer noch Double.POSITIVE_INFINITY. Diese Implementation führt Floyd Warshall zweimal durch und wenn die Pfadlänge kleiner ist als vorher, dann befinden wir uns in einem negativen Zyklus.

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; 

}