[알고리즘] 플로이드-와샬 알고리즘

정의

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 
음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 
제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다.
이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

원리

• 단방향 그래프에서의 플로이드-와샬

직접 갈 수 있는 vertex가 아니라면 INF(무한대)값으로 초기화하고 정점->정점으로의 경로가 있다면 가중치를 넣고 초기화해줌

경유해서 갈 수 있는 최단 경로가 있는 지 확인하기 위해 모든 vertex를 경유 vertex로 설정하여 모든 정점을 탐색해본다.

1번 vertex를 경유할 때의 가중치

• 4->1, 1->2 : 5+4
  arr[4][2] = min(arr[4][2], arr[4][1]+arr[1][2])

2번 vertex를 경유할 때의 가중치

1. 1->2, 2->4 : 4+1
   arr[1][4] = min(arr[1][4], arr[1][2]+arr[2][4])

2. 3->2, 2->3 : 1+1
   arr[3][3] = min(arr[3][3], arr[3][2]+arr[2][3])

3. 3->2, 2->4: 1+1
   arr[3][4] = min(arr[3][4], arr[3][2]+arr[2][4])

4. 4->2, 2->4 : 9+1
   arr[4][4] = min(arr[4][4], arr[4][2]+arr[2][4])

3번 vertex를 경유할 때의 가중치

1. 1->3, 3->2 : 1+1
   arr[1][2] = min(arr[1][2], arr[1][3]+arr[3][2])

2. 1->3, 3->4 : 1+2
   arr[1][4] = min(arr[1][4], arr[1][3]+arr[3][4])

3. 2->3, 3->2 : 2+1
   arr[2][2] = min(arr[2][2], arr[2][3]+arr[3][2])

4. 4->3, 3->2 : 5+1
   arr[4][2] = min(arr[4][2], arr[4][3]+arr[3][2])

5. 4->3, 3->4 : 5+2
   arr[4][4] = min(arr[4][4], arr[4][3]+arr[3][4])

4번 vertex를 경유할 때의 가중치

1. 1->4, 4->1 : 3+5
   arr[1][1] = min(arr[1][1], arr[1][4]+arr[4][1])

2. 2->4, 4->1 : 1+5
   arr[2][1] = min(arr[2][1], arr[2][4]+arr[4][1])

3. 3->4, 4->1 : 2+5
   arr[3][1] = min(arr[3][1], arr[3][4]+arr[4][1])

이러한 방식으로 특정 경로간의 최단 경로를 구하며 점점 먼 경로까지의 최단 경로를 이전에 구한 최단 경로를 이용해 채워나간다.

구현

public void floyd_warshall() {
	//N은 vertex의 수  graph는 각 단방향 거리를 담은 이차원 배열
    for(int k=0; k<N; k++) {
    	for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
            	graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }
}