最短路径算法的修改(从节点到自身的路由)

Question

我将全对最短路径算法(Floyd-Warshall)应用于此有向图: alt text http://www.freeimagehosting.net/uploads/99b00085bf.jpg

该图由其邻接矩阵表示.简单的代码如下所示:

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不是零,但是12,遵循B-C-E-B路线？可以通过某种方式修改邻接矩阵方法吗？

Answer 1

将对角元素邻接矩阵从0改为无穷大(理论上)应该有效.

这意味着自循环成本是无限的,并且任何其他具有小于此成本的路径更好,因此如果存在从节点到其自身的路径,通过其他节点,其成本将是有限的并且它将替换无限值.

实际上,您可以使用整数的最大值作为无限.