最短路径算法的修改（从节点到自身的路由） [英] Modification of shortest path algorithm (route from a node to itself)

问题描述

我正在应用全双工最短路径算法（ Floyd-Warshall ）到这个有向图：
alt text http：//www.freeimagehosting .net / uploads / 99b00085bf.jpg

图形由其邻接矩阵表示。简单的代码如下所示：

  public class ShortestPath {
 
 public static void main ] 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; （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] 
} 
} 
} 
} 
 
 //打印路径
 for（int r = 0; r< 5; r ++ ）{
 for（int c = 0; c <5; c ++）{
 if（D [r] [c] == x）{
 System.out.print（n /一个）; 
} else {
 System.out.print（+ D [r] [c]）; 
} 
} 
 System.out.println（）; 
} 
} 
  

}

就算法而言，上述工作正常。

我试图表明从任何节点到自己的路径是不必须 0 ，这是在这里使用邻接矩阵所暗示的，但可以是通过其他节点的任何可能的路径：例如 B -...-...-...- B

有没有办法修改我当前的表示，以表示从最小路径说， B 到 B ，不是零，而是 12 ，紧跟着 BCEB 路线？可以通过某种方式修改邻接矩阵方法来完成？

解决方案

将对角元素邻接矩阵从0改为无穷大（理论上）应该工作

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

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

I am applying the all-pairs shortest path algorithm (Floyd-Warshall) to this directed graph: alt text http://www.freeimagehosting.net/uploads/99b00085bf.jpg

The graph is represented by its adjacency matrix. The simple code looks like this:

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(" ");
     }
}

}

The above works fine as far as the algorithm is concerned.

I am trying to indicate that a path from any node to itself is not necessarily 0, as implied by the use of the adjacency matrix here, but can be any possible path through other nodes: For example B -...-...-...-B

Is there a way to modify my current representation to indicate that a shortest path from say, B to B, is not zero, but 12, following the B-C-E-B route? Can it be done by somehow modifying the adjacency matrix method?

解决方案

Changing the diagonal elements adjacency matrix from 0 to infinity (theoretically) should work.

It means the self loop cost is infinite and any other path with less than this cost is better hence if a path exists from a node to itself, through other nodes, its cost will be finite and it will replace the infinite value.

Practically you can use maximum value of integer as infinite.

这篇关于最短路径算法的修改（从节点到自身的路由）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！