플로이드 - 워셜 알고리즘 구현

Question

나는 다음과 같은 방향 그래프 나타내는 100 × 100 인접 행렬에 대한 코드 작성했습니다 : 내가 가장 짧은 찾기 위해 플로이드 - 워셜 알고리즘을 사용하려고 시도하고있어

을 그래프에서 파란색 노드의 모든 쌍에 대한 경로. 선택한 노드에 대한 모든 쌍의 최단 경로 만 찾는 방법은 무엇입니까?

public class AdjacencyMatrix 
 
{  
 
    public static final int NUM_NODES = 100; 
 
    public static final int INF = Integer.MAX_VALUE; 
 
    
 
    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 void floydWarshall(int[][] adjMat, int N) 
 
    { 
 
    \t adjMat = new int[N][N]; 
 
\t  initialize(adjMat, NUM_NODES); 
 

 
     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]); 
 
    } 
 
} 
 
} 
 

 
    } 
 

 
    public static void main(String[] args) 
 
    { 
 

 
     int adjMat[][] = new int[NUM_NODES][NUM_NODES]; 
 
     initialize(adjMat, NUM_NODES); 
 
     
 
     int A,B,C,D,E,F,G,H,I,W; 
 
     
 
     A = 20; 
 
     B = 18; 
 
     C = 47; 
 
     D = 44; 
 
     E = 53; 
 
     F = 67; 
 
     G = 95; 
 
     H = 93; 
 
     I = 88; 
 
     W = 66; 
 
     
 
     System.out.println(adjMat[A][B]); 
 

 
     System.out.println(); 
 
    } 
 
}

Answer 1

최단 플로이드 - Warshall 너 한테의 된 구현 : 여기에 내가 지금까지 작성한 코드의

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]); 
     } 
    } 
} 

케이드의이 조각을 실행 한 후 adjMat 모든 사이의 최단 거리를 포함합니다 한 쌍의 노드.

업데이트 : 정수 오버플로를 방지하려면 행렬을 Integer.MAX_VALUE/2으로 채 웁니다. 일반적으로 가능한 최대 값을 변수로 무한대로 설정하는 것은 위험합니다. 왜냐하면 추가 연산을 수행 할 수 없기 때문입니다.

Answer 2

우선 floydWarshall()의 adjMat 매개 변수에 새 값을 할당하면 안됩니다. 값을 저장하면 메서드가 종료 된 후에 저장되지 않기 때문입니다.

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