Floyd-Warshall负循环.如何找到所有未定义的路径？

Question

我已经实现了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之间的最短长度.

我在考虑测试每一条路径,但这可能太慢了.必须有一些标准的方法来解决这个问题,对吧？

谢谢

Answer 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

我认为它应该工作,它似乎也有效.