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

mseln picture mseln · Mar 29, 2013 · Viewed 13.5k times · Source

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

mseln picture mseln · Mar 30, 2013

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.