[ 알고리즘 ] Dynamic Programming : Floyd Warshall Alg

1. 문제정의

모든 노드 쌍들마다의 최단경로 구하기
(path까지는 어렵기 때문에 길이만 구할 것이다)

undirect 그래프라고 가정.
가장 쉬운방법은 다익스트라 알고리즘을 n번 돌리는 것이다.

2. Floyd Warshall Alg

각 노드별로 번호를 부여했다고 가정하자.
i → j로 가는 최단경로를 구할 건데, {1, 2, ..., k}번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다.
이 과정을 k가 0부터 N까지 반복한다. (k가 n일 때가 최종 답이된다,)
즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 k번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다.

k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다.
direct edge가 없다면 답은 무한대이다.

k가 1일때는 1번 노드를 지나갈수 있다. direct edge와 1번 노드를 지나가는 방법 중 더 저렴한 값을 저장한다.
k가 2일 때는 아래와 같은 경우의 수가 생긴다.

• direct edge (k가 1일때 수행)
• 1만 거치는 방법 (k가 1일때 수행)
• 2만 거치는 방법
• 1,2를 거치는 방법
• 2,1를 거치는 방법

위의 경우의 수 중 최소값을 다시 저장하면 된다.

즉, k까지 사용 가능할때 k를 쓰는 경우와 쓰지 않는 경우로 나눠서 더 짧은 경로를 구하면 된다.

3. code

D[n + 1][n + 1][n + 1] 는 첫번째 배열은 k번째 시행, 즉 k까지 쓸 수 있는 경우이고
두번째 세번째는 edge weight이 2차원 배열처럼 들어가 있다.

int D[n + 1][n + 1][n + 1];  

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		D[0][i][j] = W[i][j]; //그래프 값 삽입

for (k = 1; k <= n; k++)
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			D[k][i][j] = min(D[k - 1][i][j], D[k - 1][i][k] + D[k - 1][k][j]);
            //k번째를 포함하지 않는 경로 vs k번재를 포함 하는 경우

위 방법보다 메모리를 더 절약할 수 있는 코드가 있다.

아래 코드를 보면 3차원 배열 대신에 2차원 배열을 사용하였다.
이렇게 쓸 수 있는 이유는 D[k][i][k] == D[k-1][i][k] 이기 때문이다.

int D[n + 1][n + 1];

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		D[i][j] = W[i][j];

for (k = 1; k <= n; k++)
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			D[i][j] = min(D[i][j], D[i][k] + D[k][j]);