플로이드-와샬 알고리즘이란 ?

• 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘이다.
• 이때, 모든 노드에서 다른 모드 노드까지 최단 경로를 모두 계산하는 알고리즘이다.

플로이드-와샬 알고리즘의 핵심

• 거쳐가는 정점을 기준으로 최단거리를 구한다.
• a에서 b까지의 최단 경로를 구할 수 있는 경우
  • a에서 b로 바로 갈 수 있는 경우
  • a에서 k를 거쳐 b로 가는 경우
  • 위 두 개의 경우 중 최소 비용을 최단거리로 선정한다.

플로이드-와샬 소스 코드

public class FloydWarshall {
	
	static int number = 4; // 노드가 4개 
	static int INF = 10000000; // 무한대 
	
	// 초기 그래프 
	static int[][] graph = {
		{0, 5, INF, 8},
    {7, 0, 9, INF},
    {2, INF, 0, 4},
    {INF, INF, 3, 0}
  };
  
  public static void floydWarshall() {
  
	  // 결과 그래프 배열 초기화
	  int[][] result = new int[number][number];
	  
	  // 기존 그래프 복사를 결과 그래프에 복사
	  for (int i = 0; i < number; i++) {
		  for (int j = 0; j < number; j++) {
			  result[i][j] = graph[i][j];
			 }
	  }
	  
	  // k = 거쳐가는 노드
	  for (int k = 0; k < number; k++) {
		  // i = 출발 노드
		  for (int i = 0; i < number; i++) {
			  // j = 도착 노드
			  for (int j = 0; j < number; j++) {
				  if (result[i][k] + result[k][j] < result[i][j]) {
					  result[i][j] = result[i][k] + result[k][j];
					}
				}
			}
		}
		
		// 결과 출력 
		for (int i = 0; i < number; i++) {
        for (int j = 0; j < number; j++) {
             System.out.printf("%3d ", d[i][j]);
       }
         System.out.println();
    }
    
    public static void main(String[] args) {
        floydWarshall();
    }
}