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

问题描述

我申请的所有点对最短路径算法（弗洛伊德 - 沃肖尔）这个有向图：

I am applying the all-pairs shortest path algorithm (Floyd-Warshall) to this directed graph:

该图将重新由它的邻接矩阵psented $ P $。简单的code是这样的：

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.

我想表明，从任何节点的路径本身的不可以不一定 0 ，所隐含的利用邻接矩阵在这里，但可以通过其他节点的任何可能的路径：例如 B -...-...-...-乙

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

有没有办法来改变我目前的再presentation，表明从说， B 的最短路径为 B ，不为零，但 12 的 BCEB 航线以下？它可以通过某种方式修改邻接矩阵的方法来完成？

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?

推荐答案

更​​改对角线元素邻接矩阵从0到无穷远（理论上）应该工作。

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屋！