すべてのペアの最短パスの問題

Question

私は隣接ノードを使用して100ノードのグラフを実装するこのプログラムを作成しました。また、Floyd-Warshallアルゴリズムを使用して、100個のノードすべてに対して最短パスのペアをすべて見つけました。今、私はpublic static final int A = 100 ... public static final int W = 66で指定された10のインデックスのためのすべてのペアの最短パスのみを含む10×10マトリックスに100×100行列を凝縮したいと思います。どのように配列を凝縮すべきですか？私はarrayCondenserという新しいメソッドの構築を始めましたが、これを行う簡単な方法はありますか？

public class AdjacencyMatrix 
{  
    public static final int NUM_NODES = 100; 
    public static final int INF = 99999; 

    public static final int A = 20; 
    public static final int B = 18; 
    public static final int C = 47; 
    public static final int D = 44; 
    public static final int E = 53; 
    public static final int F = 67; 
    public static final int G = 95; 
    public static final int H = 93; 
    public static final int I = 88; 
    public static final int W = 66; 

    public static boolean even(int num) 
    { 
     return num%2==0; 
    } 

    public static boolean odd(int num) 
    { 
     return num%2==1; 
    } 

    public static void initialize(int [][] adjMat, int N) 
    { 
     for(int i = 0; i < N; i++) 
      for(int j = 0; j <N; j++) 
       adjMat[i][j]=INF; 

     for(int x = 0; x<N; x++) 
     { 
      int row = x/10; 
      int column = x%10; 

      if (even(row)) { 
       if (column!=9) 
        adjMat[x][x+1]=1; 
      } 
      if (odd(row)) { 
       if (column!=0) 
        adjMat[x][x-1]=1; 
      } 
      if (even(column)){ 
       if (row!=9) 
        adjMat[x][x+10]=1; 
      } 
      if (odd(column)) { 
       if (row!=0) 
        adjMat[x][x-10]=1; 
      } 
     } 
    } 

    public static int[][] floydWarshall(int[][] adjMat, int N) 
    { 
     adjMat = new int[N][N]; 
     initialize(adjMat, N); 

     for(int k = 0; k < N; ++k) 
     { 
      for(int i = 0; i < N; ++i) 
      { 
       for(int j = 0; j < N; ++j) 
       { 
       adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]); 
       } 
      } 
     } 

     return adjMat; 
    } 

    public static int[][] arrayCondenser(int[][] adjMat, int N) 
    { 
     int[] array = {A,B,C,D,E,F,G,H,I,W}; 
     adjMat = floydWarshall(adjMat, N); 




     return adjMat; 
    } 

    public static void printGrid(int[][] adjMat) 
    { 
     for (int i=0; i<NUM_NODES; ++i) 
     { 
      for (int j=0; j<NUM_NODES; ++j) 
      { 
       if (adjMat[i][j]==INF) 
        System.out.printf("%5s", "INF"); 
       else 
        System.out.printf("%5d",adjMat[i][j]); 
      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) 
    { 

     int adjMat[][] = new int[NUM_NODES][NUM_NODES]; 
     adjMat = floydWarshall(adjMat, NUM_NODES); 

     printGrid(adjMat);    

     System.out.println(); 
    } 
} 

Answer 1

あなたがしようとしているとは考えられません。 Floyd-Warshallアルゴリズムは、以前の頂点を使用して各最短経路を（あなたが知っているように）繰り返し考慮します。頂点を（そしてプロキシ、エッジによって）削除すると、それらの頂点を含む場合と含まない場合がある最短パスの有効なシナリオが削除されます。

使用している頂点のセットを変更したら、新しいグラフの最短パスを再計算する必要があります。それ以外の場合は、基本的にすべての単一パスを追跡して、頂点を削除したときにそれらの頂点を使用したパスを削除し、新しい最短パスを作成できるようにする必要があります。