Shortest Path (3)
Floyd-Warshall Algorithm
- all-to-all 최단 경로 알고리즘들 중 가장 유명하다.
- Floyd 알고리즘은 동적 계획법(Dynamic Programming) 전략에 기반하고 있다.
- 가중치 방향 그래프 G = (V, E) (V = {1, 2, ... , n})
- 모든 노드 쌍들간 최단 경로의 길이를 구한다.
- $d^k$[i, j]
중간에 노드 집합 {1, 2, ... , k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단 경로의 길이를 뜻한다.
1) $d^0$[i, j]는 k가 0인 경우로 공집합을 의미한다. 또한 중간에 지날 수 있는 노드가 없다는 것으로 직접 연결된 엣지가 있지 않다면 길이를 ∞로 생각한다.
2) $d^n$[i, j]는 k가 n인 경우다. 이는 곧 아무 노드나 지나도 상관이 없다는 것과 같기 때문에 i에서 j까지 가는 최단 경로와 같다고 할 수 있으며 또한 알고리즘의 최종 목표이기도 하다.
3) $d^k$[i, j]는 1~k사이의 노드만 지날 수 있게 허용한 경우이다. 이 때는 두 가지 케이스가 존재하는데 k를 지나 목적지 j에 도달하는 경우와 그렇지 않은 경우이다.
4) k를 지나지 않는 경우 $d^{k-1}$[i,j]가 되며, k를 지날 경우 k이전까지의 노드들과 k이후 j까지의 노드들을 더한 $d^{k-1}$[i, k] + $d^{k-1}$[k, j]가 된다. $d^k$[i, j]는 두 경우 중 더 길이가 작은 경우를 선택하기만 하면 된다.
- 슈도 코드
FloydWarshall (G)
for i = 1 to n
for j = 1 to n
$d^0$[i, j] = $w_{ij}$;
for k = 1 to n // 반복을 계속하면 최종적으로 $d^n$[i, j]에 도달하게 된다.
for i = 1 to n
for j = 1 to n
//실제로 구현을 위해서는 d[k][i][j]와 같이 삼차원 배열을 사용해야 한다.
$d^k$[i, j] = min{$d^{k-1}$[i, j], $d^{k-1}$[i, k] + $d^{k-1}$[k, j]};
-> 위 코드는 삼중 반복문에 의해 O($n^3$)의 시간 복잡도를 가진다.
-> 다익스트라 또한 모든 노드에 대해 전부 알고리즘을 실행하면 O($n^3$)의 시간이 걸린다.
- 개선된 슈도 코드
위 코드와 같으나 $d^k$등 삼차원 배열 부분인 k를 제거하고 d로만 표시하여 이차원 배열로 만들어준다.
기존 가장 작았던 길이의 값들을 보존하기 위해 추가적으로 k를 사용할 것 없이 더 작은 값이 있으면 기존 값에 덮어씌우기만 하면 되기 때문에 삼차원일 필요는 없게 된다.
FloydWarshall (G)
for i = 1 to n
for j = 1 to n
$d^0$[i, j] = $w_{ij}$; // 최단 길이를 저장하는 배열
π[i, j] = null; // 최단 경로를 찾기 위한 배열
for k = 1 to n // 반복을 계속하면 최종적으로 $d^n$[i, j]에 도달하게 된다.
for i = 1 to n
for j = 1 to n
if d[i, j] > d[i, k] + d[k, j]
d[i, j] = min{d[i, j], d[i, k] + d[k, j]};
π[i, j] = k;
//s에서 t까지 가는 경로가 존재한다는 가정 하에 최단 경로상 중간노드들(s, t자신들은 제외)을 출력한다.
Print-Path (s, t, π)
if π[s, t] == null
return;
Print-path(s, π[s, t]);
print(π[s, t]);
Print-path(π[s, t], t);
