[알고리즘] 최단 경로 알고리즘(3) - 플로이드 워셜(Floyd-Warshall) 알고리즘

1. 플로이드 워셜 알고리즘이란?

다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간의 최단 경로를 구할 수 있다.

또한 플로이드-워셜 알고리즘 역시 다익스트라와는 다르게 음의 가중치를 갖는 간선이 있어도 사용 가능하다.

 

플로이드-워셜 알고리즘은 다이나믹 프로그래밍에 속하여 다음과 같은 점화식을 갖는다.

 

 

2. 진행 과정

 

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 저장하기 위해 2차원 거리 배열을 이용한다.

- 최단 거리 테이블의 초기 상태를 저장한다. 

 

- 1번 정점을 거쳐서 가는 경우에 대해 최단 거리 테이블을 갱신한다.

 

- 2번 정점을 거쳐서 가는 경우에 대한 최단 거리 테이블을 갱신한다.

 

-  3번 정점을 거쳐서 가는 경우에 대한 최단 거리 테이블을 갱신한다.

 

-  4번 정점을 거쳐서 가는 경우에 대한 최단 거리 테이블을 갱신한다.

 

---

3. 구현 (c++)

진행 과정을 보면 알겠지만, 매우 심플하다. 따라서 구현 역시 다익스트라 알고리즘에 비해 굉장히 단순하다.

 

for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
        cin >> adj[i][j];
        if(adj[i][j] == 0)
            adj[i][j] = INF;
    }
}


//플로이드-워셜
for (int k=0; k<N; k++){
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
        }
    }
}