弗洛伊德-沃歇尔与负周期。如何查找所有未定义的路径？

java shortest-path floyd-warshall

2022-09-04 21:12:28

我已经实现了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;
}

在图形上运行算法后：

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

我得到邻接矩阵：

  | 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 是负循环的一部分，它在矩阵中的位置 d[i][i] 处有一个负值。因此，如果我检查矩阵的对角线，我可以找到所有属于负循环的节点。因此，如果我们看一下上面的例子，我们可以看到节点1和2是负循环的一部分。问题是我想找到哪些路径是定义的，哪些是未定义的。如果您可以通过一个负循环从A到B，那么路径的长度应该是未定义的，因为它可以是任意小的。

所以问题是，我怎么能找到所有未定义的路径？

我希望算法返回矩阵：（而不是上面的矩阵）

  | 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

其中 d[i][j] = INF 表示 i 和 j 之间没有路径，而 -INF 表示 i 和 j 之间有任意小路径（路径在某处传递负循环），否则 d[i][j] 是 i 和 j 之间的最短长度。

我正在考虑测试每条路径，但这可能太慢了。一定有一些标准的方法可以解决这个问题，对吧？

谢谢

答案 1

好吧，我已经找到了解决我自己问题的方法。

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

我认为它应该有效，而且似乎也有效。

答案 2

我有一个视频，确切地解释了Floyd-Warshall算法是如何工作的。从本质上讲，Floyd-Warshall算法用于查找具有正或负边缘权重的加权图中所有节点对之间的最短路径。

以下算法接受邻接矩阵，其中Double.POSITIVE_INFINITY用于指示两个节点不连接。对于每个节点，您可能还需要初始化其自身的权重 0。

此方法更新初始矩阵以指示所有节点对之间的最小距离。如果最短路径任意小，则答案将存储为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;

}