Floyd-Warshall算法 - 最短路径 - 将路径索引保存到数组

Question

我为对称的无向图实现了Floyd-Warshall算法。目前，我已经计算出每个连接点的最佳路径。我的问题是，我想保存收集到累计重量的索引点，以便能够稍后写入路线中的点的名称。我想将它们保存到列表中，但我不知道应将哪些索引写入函数addDrawPointsToList（int a，int b，int [] [] M）。 a和b是点之间我想保存航点

• 0 - 在同一节点
• 1 - 有节点之间的连接
• X - 没有连接= 999重量

CODE：

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 for my english; <

Answer 1

我不知道是什么addDrawPointsToList是应该做的，但在一般情况下，如果你想要从弗洛伊德 - 沃肖尔的路径，你要记住你计算在i-th步骤是什么。

如果M[j][i] + M[i][k] < M[j][k]，然后从j到k使用节点1, ..., i最短路径经过i。因此，最短路径可以在从j到i以及从j到k的最短路径的最短路径中分解。假设A[j][k]是这个中间节点。

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

然后拿到路径从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代码来模拟这一点。