变形最短路径算法（路线从一个节点至自身）

的本人申请的所有点对最短路径算法（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路径后面？可以通过修改邻接矩阵方法来完成吗？

来源

2009-12-23 denchr

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

这意味着自我循环成本是无限的，任何其他路径的成本都低于此成本，因此如果从节点到其自身，通过其他节点存在路径，其成本将是有限的，它将取代无限值。

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

来源

2009-12-23 19:19:05 codaddict

+1该矩阵告诉算法，B-> B路径的权重为0，所以它当然是最短的。明确定义自身边的权重以赋予它们权重。 :) – PSpeed 2009-12-23 19:27:52

非常感谢提示，其实很简单。 – denchr 2009-12-23 19:56:20

变形最短路径算法（路线从一个节点至自身）

回答

相关问题