플로이드 와샬 (Floyd - Warshall)

플로이드 와샬 알고리즘은 최단경로 알고리즘중 하나이다.

정점 V개가 있고 거리가 다 주어져 있을 때 단 한 번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다.

3중 for문으로 구성되어있으므로 O(V^3) 에 동작한다.

 

동적계획법

어김없이 등장하는 동적계획법.

동적 계획법으로 문제를 풀기 위해서는 재귀 관계식을 찾고 상향식으로 표현해야한다.

 

D : 각 정점의 쌍이 가지는 최단 경로의 길이를 나타내는 행렬 이라고 하자

즉, D[i][j] : vi 에서 vj 로 가는 최단 경로의 길이이다.

 

그렇다면 가장 초기에 주어지는 정점들과 거리의 정보들을 D(0) 이라 하자

이 배열은 바로 옆 노드만 이동 가능한 행렬일 것이다.

왜냐하면 초기 정보들은 한 노드에서 다른 노드까지의 거리 정보이기 때문이다.

 

이제 k 개의 노드들을 거쳐 최단경로로 가는 정보를 구하는데, 이를 D(k) 라 하자.

 

즉, 최종적으로 구해야하는 정보는 D(n)이 되는 것이다. (n : 정점의 수)

 

점화식으로 식을 써보면

 

D(k) [i][j] = min( D(k-1) [i][j], D(k-1) [i][k] + D(k-1) [k][j] ) 이다.

즉, k번째의 정점을 지나서 i에서 j로 가는것과 원래 i 에서 j로 가는 최단경로 중에 누가더 짧은지를 계산하는 것이다.

 

코드로 보면서 이해해보자.

def floyd(w):
    // w 는 초기 정보
    d = w
    n = len(w)
    
    for k in range(n);
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

 

식에서 의문점들이 있을텐데

 

1. k가 가장 바깥 반복문인 이유

2. d배열이 하나인 이유 (위에서 언급한 d(k-1) 이나 d(k) d(n) 등)

 

우선 k가 가장 바깥 반복문인 이유는

모든 정점에 대하여 k개의 정점을 지날 때의 거리값들을 업데이트 해야 하기 때문이다.

만약 반복문이 i j k 순서라면 어떤 i j 에 대하여 0개부터 n개의 정점을 모두 지나는 경로중 최단 경로를 계산 해놓기 때문에 다른 계산에 영향을 준다.

하지만 k가 가장 바깥 쪽 이어야 모든 정점에 대해 순차적으로 업데이트 된다.

 

또한, k 반복문의 의미는, 예를들어 k=3 일때 3개의 정점을 지난다는 의미가 아니라 3번째 정점을 지난다는 의미이지만, 이전에 k 값들을 지나왔기 때문에 k개의 정점들을 지나는 경로라고 해석할 수 있다.

 

d배열이 하나인 이유는 마찬가지로 k 반복문에서 d(k)를의미하고, k값이 증가하면 d(k+1)로 업데이트 된다고 이해할 수 있다. ( 슬라이딩 윈도우 )