Floyd-Warshall Algorithm

 

  Floyd Warshall 알고리즘은 다익스트라 알고리즘의 진화(?) 버전으로 가중치가 주어진 그래프에서 모든 정점으로부터 모든 정점으로까지의 최소 거리를 구하는 알고리즘이다. Floyd Warshall 알고리즘은 모든 거쳐가는 정점을 기준으로 DP처럼 동작해 구현이 매우 간단하다.

 

1) Floyd Warshall 알고리즘의 동작

 floyd warshall 알고리즘은 다음과 같이 동작한다.

let) $d[i][j] :=$ ($i$부터 $j$까지의 최소거리 배열)
let) $graph[i][j] :=$ ($i$와 $j$를 연결한 간선의 가중치) -> 연결이 안될 경우 INF(∞)
1) $d[i][j]$ 초기화 
$$d[i][j] = \begin{cases}0 & i=j\\graph[i][j] & otherwise\end{cases}$$
2) $1\leq v \leq N$ 를 거쳐가는 정점으로 설정(for문)
3) $1\leq i,j \leq N$ 에 대해 $d[i][j]$ 업데이트
$$d[i][j] = \min(d[i][j],d[i][v]+d[v][j])$$

 $O(N)$짜리 반복문 3개가 돌아가므로 시간복잡도는 $O(N^3)$으로 상당히 느린 편이다.

 

2) Floyd Warshall 알고리즘 코드

void floyd(){
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

 동작하는 그대로 구현만 하면 되서 매우 쉽다.