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을 할 예정이다 모르겠어요,하지만 당신은 플로이드 - Warshall에서 경로를 검색하려는 경우 일반적으로, 당신이 i-th 단계에서 계산하는 것을 명심해야합니다.

는 M[j][i] + M[i][k] < M[j][k] 경우, 노드 1, ..., i를 사용하여 k-j에서 최단 경로는 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) 
} 

이 주요 아이디어, 지금 당신이 시뮬레이션 자바 코드를 작성할 수 있습니다.