플로이드-워셜 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm})은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 변도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

개요[편집]

플로이드-워셜 알고리즘은 동적 계획법 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최소 비용을 구한다. 여기에 경유지를 기록하면 최소 비용 경로까지 구할 수 있다. 플로이드-워셜 알고리즘은 다음과 같은 접근으로 설계되었다.

  • 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.
  • 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다.

이는 중첩된 부분문제로 볼 수 있으며 동적 계획법을 적용하여 효과적으로 접근할 수 있다. 한편 비용을 구하는 김에, 어떤 경유지를 지나서 최소 비용을 만들었는지 기록해두면, 최소 비용 뿐만 아니라 최소 비용 경로까지도 구할 수 있다. 플로이드-워셜 알고리즘을 의사코드로 표현하면 아래와 같다.

1 procedure floyd-warshall(두 정점을 잇는 모서리의 가중치 테이블 W)
2     D : 두 정점을 잇는 경로의 최소 비용 테이블. 모든 성분을 ∞로 초기화
3     M : 두 정점을 지나가는 최소 비용 경로가 거쳐야 할 마지막 경유지 테이블. 모든 성분을 null로 초기화
4     for i from 1 to |V|
5         for j from 1 to |V|
6             D[i][j] := W[i][j]
7     for v from 1 to |V|
8         D[v][v] := 0
9     for k from 1 to |V|
10        for i from 1 to |V|
11            for j from 1 to |V|
12                if D[i][j] > D[i][k] + D[k][j]
13                    D[i][j] := D[i][k] + D[k][j]
14                    M[i][j] := k
15    return D

이렇게 구한 비용 & 경유지를 활용하여 경로를 복구하는 알고리즘은 아래와 같다.

1 procedure floyd-warshall-path(정점 v1, 정점 v2, 경유지 테이블 M)
2     S : 경로를 역으로 저장하는 스택
3     P : 경로
4     S.push(v2)
5     while M[v1][S.top()]
6         S.push(M[v1][S.top()])
7     while ~S.empty()
8         P.add(S.top())
9         S.pop()
10    return P

계산 복잡도[편집]

플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 O(|V|^3)시간 복잡도를 갖는다. 경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 O(|V|)의 시간 복잡도를 갖는다. 종종 다익스트라 알고리즘과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다.

소스 코드[편집]

C 언어[편집]

int d[N][N];   // Cost Table. d[v1][v2] : Minimum cost of path v1 -> v2
int via[N][N]; // Via Table.
void doFloyd()
{
    // Initialize
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            d[i][j] = via[i][j]; // k = 0
        }
    }
 
    // Do Floyd-Warshall Algorithm
    for (int k = 0; k < N; ++k)
    {
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if (d[i][j] > d[i][k] + d[k][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    via[i][j] = k;
                }
            }
        }
    }
}