java 具有负循环的 Floyd-Warshall。如何找到所有未定义的路径？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15709277/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Floyd-Warshall with negative cycles. How do I find all undefined paths?
提问by mseln
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.
我已经实现了 Floyd Warshall 算法并且它有效，但问题是我不知道如何找到所有未定义的路径。我在网上搜索过，但我只能找到如何检测图形是否有负循环的答案。
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.
我知道如果节点 i 是负循环的一部分，它在矩阵中的位置 d[i][i] 处具有负值。因此，如果我检查矩阵的对角线，我可以找到所有属于负循环的节点。因此，如果我们查看上面的示例，我们可以看到节点 1 和 2 是负循环的一部分。问题是我想找到哪些路径已定义，哪些未定义。如果您可以通过负循环从 A 到 B，那么路径的长度应该是未定义的，因为它可以是任意小的。
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.
其中 d[i][j] = INF 表示 i 和 j 之间没有路径，-INF 表示 i 和 j 之间存在任意小路径（路径在某处通过负循环），否则为 d[i ][j] i 和 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
谢谢
采纳答案by mseln
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.
我认为它应该有效，而且似乎也有效。
回答by will.fiset
I have a videothat 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.
我有一个视频，它准确地解释了 Floyd-Warshall 算法的工作原理。本质上，Floyd-Warshall 算法用于在具有正或负边权重的加权图中找到所有节点对之间的最短路径。
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.
下面的算法接受一个邻接矩阵，其中 Double.POSITIVE_INFINITY 用于表示两个节点没有连接。对于每个节点，您还可能希望为其自身初始化 0 的权重。
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.
此方法更新初始矩阵以指示所有节点对之间的最小距离。如果最短路径任意小，则答案存储为 Double.NEGATIVE_INFINITY。如果两个节点无法相互到达，那么它仍然是 Double.POSITIVE_INFINITY。此实现运行 Floyd Warshall 两次，如果路径长度比以前小，那么我们处于负循环。
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;
}
回答by daltonfury42
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.
只要输入图中不存在负循环，Floyd-Warshall 算法就会输出正确的结果。如果存在负循环，计算最短（简单）路径是一个 NP-hard 问题，Floyd-Warshall 算法不会输出正确的结果。
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:
但是可以通过检查矩阵的对角线上是否存在负项来检测负循环的存在。这是在该算法的第 8 行和第 9 行中完成的：
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')
