Floyd-Warshall with negative cycles. How do I find all undefined paths?

Question

I have implemented the Floyd Warshall algorithm and it works, but the problem is that I don't know how I can find all paths which are not defined. I have searched around the web but I can only find answers to how to detect if a graph has negative cycles or not.

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

After running the algorithm on the graph:

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

I get the adjacency matrix:

  | 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 

I know that if node i is part of a negative cycle it has a negative value at position d[i][i] in the matrix. So if I check the diagonal of the matrix I can find all nodes which are part of a negative cycle. So if we look in the example above, we can see that node 1 and 2 are parts of a negative cycle. The thing is that I want to find which paths that are defined and which that are not defined. If you can come from A to B trough a negative cycle then the length of the path should be undefined since it can be arbitrary small.

So the question is, how can i find all undefined paths?

I want the algorithm to return the matrix: (instead of the one above)

  | 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 

Where d[i][j] = INF means that there is no Path between i and j, and -INF means that there's an arbitrary small path between i and j (the path passes a negative loop somewhere) and otherwise is d[i][j] the shortest length between i and j.

I was thinking of test every single path, but that would probably be too slow. There must be some standard way to solve this problem, right?

Thank you

Answer 1

Well I have found a solution to my own problem.

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

I think it should work and it seems to work too.

Answer 2

I have a video that explains exactly how the Floyd-Warshall algorithm works. In essence, the Floyd-Warshall algorithm is used to find the shortest paths between all pairs of nodes in a weighted graph with positive or negative edge weights.

The following algorithm accepts an adjacency matrix, where Double.POSITIVE_INFINITY is used to indicate that two nodes do not connect. For each node, also you'll likely want to initialize a weight of 0 to itself.

This method updates the initial matrix to indicate the minimum distance between all pairs of nodes. If the shortest path is arbitrarily small, then the answer is stored as Double.NEGATIVE_INFINITY. If two nodes cannot reach each other then it is still Double.POSITIVE_INFINITY. This implementation runs Floyd Warshall twice and if the path length is smaller than it was before then we are in a negative cycle.

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;

}

Answer 3

The Floyd-Warshall algorithm outputs the correct result as long as no negative cycles exist in the input graph. In case that a negative cycle exists, computing a shortest (simple) path is an NP-hard problem and the Floyd-Warshall algorithm will not output the correct result.

But it is possible to detect the presence of a negative cycle by checking that there is a negative entry in the diagonal of the matrix. This is done in line 8 and line 9 of this algorithm:

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