所有對最短路徑問題

我已經編寫了這個程序，該程序使用鄰接矩陣實現了具有100個節點的圖。我還使用Floyd-Warshall算法爲所有100個節點找到所有最短路徑對。現在，我想將100 x 100矩陣壓縮爲10 x 10矩陣，該矩陣僅包含public static final int A = 100 ... public static final int W = 66指定的10個索引中的所有配對最短路徑。我應該如何壓縮陣列？我已經開始構建一種名爲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(); 
    } 
}

來源

2017-03-06 Nate

我不認爲你想要做什麼是可能的。 Floyd-Warshall算法使用以前的頂點迭代地（如你所知）考慮每條最短路徑。一旦刪除頂點（並通過代理，邊），那麼您將刪除可能包含或不包含這些頂點的最短路徑的有效方案。

一旦你改變了你正在使用的頂點集，你將不得不重新計算新圖的最短路徑。否則，你基本上必須跟蹤每一條路徑，這樣當你刪除頂點時，你可以刪除任何使用這些頂點的路徑 - 從而得到新的最短路徑。

來源

2017-03-06 15:59:44 ryuu9187

所有對最短路徑問題

回答

相關問題