[algorithm] Floyd-Warchall algorithm

 
 
Floyd-Warchall 알고리즘
그래프에서 모든 노드 간의 최단경로를 찾는 r다이나믹 프로그래밍 기법이다. 보통 플로이드 와샬 알고리즘을 다루기 전에 다익스트라 부터 공부하는데, 알고리즘 수업이 반대로 학습해서 나도 플로이드와샬부터 정리하겠다. 
 
 

1. 문제 상황

가중치가 있는 그래프에서 모든 노드 간 최단경로를 찾는다. 

1에서부터 5로 간다고 생각해보자. 
그럼 1 -> 2 -> 4 -> 5 로 갈 수도 있고, 1-> 3-> 2-> 4-> 5로 갈 수도 있다. 비용만 살펴보면 첫번째 경우는 1+2+4=7의 비용이 발생하고 두번째 경우는 12의 비용이 발생한다. 즉, 1에서 5로 가는 최단경로는 1 - 2- 4- 5라는 것을 알 수 있다. 
알고리즘 초심자에게 이걸 설명해주면 반정도의 사람들은 의문을 가진다 
"그냥 지나는 정점이 가장 작은 것 중에 최소 값을 구하면 안되는건가?"
아래 그림을 보자.

1 에서 3으로 가는 최단 경로는 1에서 3으로 바로 가는게 아니라 1 -> 2 -> 3이다. 즉, 거치는 정점의 수가 적다고 짧은 거리가 아니라는 것이다. 
다익스트라는 1개의 정점에서의 최단거리를 구했다. 플로이드 와샬 알고리즘은 모든 정점간의 최단거리를 알 수 있다. 
(다익스트라 업데이트 후 링크 업로드 예정)

2. 문제 해결 방식

graph[i][j] : i에서 j로 이동할 때의 비용
무방향 그래프일 때는 graph[i][j] == graph[j][i]

자기자신은 0, 이동할 수 없는 (연결되지 않은) 노드끼리는 INF 로 채운다.
이렇게 완성된 그래프는 지금까지 계산된 노드간의 최소비용이다. 하지만 아직까지는 직접 연결된 값만 비교했다. 지금부터 한 노드를 거쳐갔을 때를 비교하여 더 작은 값으로 업데이트 할 것이다. 
위 그래프에서 1->4를 생각해보자. graph[1][4] = INF였다. 즉, 연결된 곳이 없었다.
그럼 다른 노드들 (1,2,3,4,5)를 생각해보자.
graph[1][1] + graph[1][4] = 0 + INF = INF
graph[1][2] + graph[2][4] = 1 + 2 = 3
graph[1][3] + graph[3][4] = 3 + INF = INF
graph[1][4] + graph[4][4] = INF + 0 = INF
graph[1][5] + graph[5][4] = INF + 4 = INF

위의 값을 보면, 2을 거쳐갈 때가 가장 작은 것을 알 수 있다. 그럼 graph[1][4]를 3으로 교체할 수 있다. 이렇게 모든 노드에 대해 거쳐하는 수를 점검해보면된다. (+ 무방향 그래프는 graph[i][j]와 graph[j][i]의 값이 같으니 둘 다 업데이트 해도 된다.)

• 1을 거쳐가는 경우
  graph[1][1] vs graph[1][1] + graph[1][1]
  graph[1][2] vs graph[1][1] + graph[1][2]
  ...
  graph[5][5] vs graph[5][1] + graph[1][5]
  
  

• 2를 거쳐가는 경우
  graph[1][1] vs graph[1][2] + graph[2][1]
  graph[1][2] vs graph[1][2] + graph[2][2]
  ...
  graph[5][5] vs graph[5][2] + graph[2][5]
  
  
• 3을 거쳐가는 경우
  graph[1][1] vs graph[1][3] + graph[3][1]
  graph[1][2] vs graph[1][3] + graph[3][2]
  ...
  graph[5][5] vs graph[5][3] + graph[3][5]
  
  
• 4를 거쳐가는 경우
  graph[1][1] vs graph[1][4] + graph[4][1]
  graph[1][2] vs graph[1][4] + graph[4][2]
  ...
  graph[5][5] vs graph[5][4] + graph[4][5]
  
  
• 5를 거쳐가는 경우
  graph[1][1] vs graph[1][5] + graph[5][1]
  graph[1][2] vs graph[1][5] + graph[5][2]
  ...
  graph[5][5] vs graph[5][5] + graph[5][5]

규칙이 보이는가?
k를 거쳐가는 경우를 비교하려면 min(graph[i][j] , graph[i][k] + graph[k][j] ) 하면 된다. 
이렇게 비교하여 채운 최종 표는 아래와 같다.

 

3. 코드

예전에 c++로 짜둔 코드가 있어서 핵심 부분만 올린다.

for (int k = 1; k <= n; k++){
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++)
				graph[i][j] = min(graph[i][j], (graph[i][k] + graph[k][j]));
		}
	}

위의 설명을 잘 따라왔다면 무리없이 코드를 해석할 수 있을 것이라 생각한다.
 

4. 활용 문제

https://www.acmicpc.net/problem/11404

11404번: 플로이드