Floyd-Warshallアルゴリズム - 最短パス - パスへのインデックスを配列に保存

Question

私はFloyd-Warshallアルゴリズムを対称で無向グラフに実装しています。現時点では、各接続ポイントの最適なパスが計算されています。私の問題は、後でルートからポイントの名前を書くことができるように、累積されたウェイトに課金されたインデックスポイントを保存したいということです。私はそれらをリストに保存したいが、どのインデックスを関数addDrawPointsToList（int a、int b、int [] [] M）に書き込むべきか分からない。 A及びBはポイントは、その間私はウェイポイント

• 0を保存したいです - 同じノード
• 1 - ノード間の接続がある
• X - 接続なし= 999重量

コード：

public class FloydWarshallAlg { 
static int[][] P; 
static List<Integer> lista; 
static final int N = 43; 
static final int X = 999; 

public static void main(String[] args) { 

    int M[][] = new int[][]{ 
     {0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {1, 0, 1, X, X, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, 1, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, 1, X, 0, X, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, 1, 1, X, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, 1, X, X, 0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, 1, X, X, 1, 0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, 1, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, 1, 1, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, X, X, 0, 1, X, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, X, X, 1, 0, 1, X, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, 1, 1, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X}, 
     {X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0}}; 

    lista = new ArrayList<Integer>(); 
    System.out.println("Main Matrix."); 
    printMatrix(M); 
    System.out.println("Shortest Path Matrix."); 
    printMatrix(FloydAlgo(M)); 
    addDrawPointsToList(3, 12); 
    printList(lista); 
} 

public static List addDrawPointsToList(int a, int b, int[][] M) { 

    return lista; 
} 

public static int[][] FloydAlgo(int[][] M) { 
    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < N; j++) { 
      for (int k = 0; k < N; k++) { 
       // to keep track.; 
       if (M[j][i] + M[i][k] < M[j][k]) { 
        M[j][k] = M[j][i] + M[i][k]; 
       } 
      } 
     } 
    } 
    return M; 
} 

public static void printMatrix(int[][] Matrix) { 
    System.out.print("\n\t"); 
    for (int j = 0; j < N; j++) { 
     System.out.print(j + "\t"); 
    } 
    System.out.println(); 
    for (int j = 0; j < 347; j++) { 
     System.out.print("-"); 
    } 
    System.out.println(); 
    for (int i = 0; i < N; i++) { 
     System.out.print(i + " |\t"); 
     for (int j = 0; j < N; j++) { 
      if (Matrix[i][j] == 999) { 
       System.out.print("X"); 
      } else { 
       System.out.print(Matrix[i][j]); 
      } 
      System.out.print("\t"); 
     } 
     System.out.println(""); 
    } 
    System.out.println("\n"); 
} 

public static void printIntArray(int A[]) { 
    for (int i = 0; i < N; i++) { 
     System.out.print(A[i] + " "); 
    } 
} 

public static void printList(List L) { 
    for (int i = 0; i < L.size(); i++) { 
     System.out.print(L.get(i) + ", "); 
    } 
    System.out.println("\nList size: " + L.size()); 
}} 

私はこれが解決すべき小さな問題だと思っていますが、私は初心者のプログラマーであり、解決策は見当たりません。私はどんなアドバイスにも感謝しています。 私の英語のためにSry; <

Answer 1

私はaddDrawPointsToListが行うことになっているのか分からないが、あなたはフロイド・ウォーシャルからのパスを取得する場合、一般的に、あなたはi-thステップで計算するものを心に留めておく必要があります。

はM[j][i] + M[i][k] < M[j][k]場合、ノード1, ..., iを用いkからjから最短経路はi通過します。したがって、最短経路は、jからiまで、最短経路はjからkまでの最短経路で分解することができる。 A[j][k]をこの中間ノードにします。その後iからkへのパスを取得する

if (M[j][i] + M[i][k] < M[j][k]) { 
    A[j][k] = i; 
    M[j][k] = M[j][i] + M[i][k]; 
} 

：これは主要なアイデアである

get_path(s, t) { 
    if A[s][t] = s or A[s][t] = t then return [s] 
    // + is here the concatenation 
    return get_path(s, A[s][t]) + get_path(A[s][t], t) 
} 

、今はこれをシミュレートするためのJavaコードを書くことができます。