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
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.