最短路径算法的修改（从一个节点到自身的路径）

Question

我正在应用全源最短路径算法（Floyd-Warshall）到这个有向图中： 该图由其邻接矩阵表示。简单的代码如下：

public class ShortestPath {

public static void main(String[] args) {
    int x = Integer.MAX_VALUE;
    int [][] adj= {      
      {0, 6, x, 6, 7}, 
            {x, 0, 5, x, x}, 
            {x, x, 0, 9, 3}, 
            {x, x, 9, 0, 7}, 
            {x, 4, x, x, 0}};

    int [][] D = adj;

    for (int k=0; k<5; k++){
        for (int i=0; i<5; i++){
            for (int j=0; j<5; j++){
                if(D[i][k] != x && D[k][j] != x && D[i][k]+D[k][j] < D[i][j]){
                       D[i][j] = D[i][k]+D[k][j];                    
                   }
            }
        }       
    }

    //Print out the paths
    for (int r=0; r<5; r++) {
         for (int c=0; c<5; c++) {
             if(D[r][c] == x){
                 System.out.print("n/a"); 
             }else{
             System.out.print(" " + D[r][c]);
             }
         }
         System.out.println(" ");
     }
}

就算是算法没问题，这样的方法依然无法表达从任何节点到自身的路径不一定是0，因为可以通过其他节点连接来实现。例如：B -...-...-...-B

请问是否有办法修改当前表示方式，以表达从B到B的最短路径不是0而是12，沿着B-C-E-B这条路线？是否可以通过修改邻接矩阵的方法来实现？

- denchr

Answer 1

将邻接矩阵的对角元素从0修改为无穷大（理论上）应该是有效的。

这意味着自环的成本是无限的，而任何其他成本低于此成本的路径都更好，因此，如果存在一条从一个节点经过其他节点返回自身的路径，则其成本将是有限的，并且它将替换无限值。

实际上，您可以使用整数的最大值作为无穷大。

- codaddict

---

+1 矩阵告诉算法B->B路径的权重为0，因此它总是最短的。明确定义自环的权重以赋予它们权重。 :) - PSpeed