4

この有向グラフに 、すべてのペアの最短経路アルゴリズム（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がゼロではなく12、ルートをたどることを示す方法はありB-C-E-Bますか？隣接行列法をどうにかして修正することでそれを行うことができますか？

4

1 に答える 1

12

対角要素の隣接行列を0から無限大に（理論的には）変更すると機能するはずです。

これは、自己ループのコストが無限であり、このコストよりも小さい他のパスの方が優れていることを意味します。したがって、ノードから他のノードを経由してそれ自体にパスが存在する場合、そのコストは有限になり、無限の値に置き換わります。

実際には、整数の最大値を無限大として使用できます。

于 2009-12-23T19:19:05.920 に答える