[최단경로] 04. 플로이드 워셜

이번에는 최단 경로의 마지막 알고리즘인 플로이드 워셜 알고리즘에 대해서 살펴보자.

 

플로이드 워셜 알고리즘

 

플로이드 워셜의 특징

이제까지 다익스트라와 벨만포드 알고리즘을 이용한 최단 경로를 구해봤다. 한 점에서 모든 점까지의 최단 거리를 구할 수 있었고 여차하면 음의 간선까지 처리할 수 있었는데 또 필요한 최단 거리 알고리즘이 있을까?

있으니까 여기서 글을 쓰고 있다. ㅎ

이번에 알아볼 알고리즘은 플로이드 워셜 알고리즘이다. 플로이드는 이전까지의 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단거리를 구하기 위한 알고리즘이다.

물론 다익스트라, 벨만포드의 모든 정점을 출발점으로 해서 N번 돌리면 모든 정점에서의 최단거리를 구할 수 있다. 하지만 플로이드 워셜은 대체로 다익스트라, 벨만포드를 N번 돌릴 때보다 빠르고 무엇보다 코드가 엄청 간단해서 실수하기 힘들다는 장점이 있다.

 

경유지 개념의 활용

플로이드는 알고리즘 전개를 위해 경유지(v)라는 개념을 사용한다. 즉 시작점(f)에서 도착점(t)까지 이동하는 경로가 있을 때 출발점과 도착점을 제외하고 지나게 되는 정점들을 경유지라고 한다.

이제 아래와 같은 표현을 정의해보자.

Dv(t, f) : 정점의 집합 v까지의 정점들을 경유지로 고려했을 때 f(출발점)에서 t(도착점)로 가는 최단 경로

여기서 중요한 점은 v의 요소들을 모두 사용해야 하는 것은 아니며 그 정점들까지를 고려하는 상황이라는 점이다.

 

다음은 정점과 간선 정보가 주어졌을 때 a에서 f로 이동하기 위한 D 를 찾아가는 과정이다.

 

추가로 알 수 있는 사항들

D를 정의하면서 다음의 두 가지 사항을 기본적으로 정리할 수 있다.

• D[](f, t): 출발점(f)에서 도착점(t)로 가는 경로 중 경유점이 없는 최단 경로로 간선의 길이를 의미한다.
• D[](f, f): 출발점(f)과 도착점(f)이 같은 경우로 이때의 비용은 0 이다.

 

전개 방식

 

플로이드 워셜은 DP

플로이드 워셜은 DP를 통해서 문제를 해결한다. 즉 작은 부분문제에서 출발해서 큰 전체 문제를 해결하는 형식이다. 출발지(f)에서 목적지(t)까지 경유지(a) 하나를 고려하는 경우를 생각해보자.

이 경우 f->t로 가는 비용 D[a](f, t)는 직접 가거나 a라는 경유지를 거쳐가거나 둘 중의 하나이다. 이 비용은 t->f로 직접 연결하는 경우 즉 D[](f, t)와 f->a의 비용인 D[](f, a) + a->t의 비용인 D[](a, t)의 합 중 작은 값이다.

(D[a](f, t)가 a를 반드시 거쳐야 하는 것이 아니라 a까지를 고려한 것이라는 내용을 상기시키자.)

 

이제 f에서 a 경유지를 고려했을 때 t까지 가는 최소 거리를 구했다. 그럼 문제를 좀 더 크게 만들어서 b까지의 경유지를 고려해서 즉 a, b 두 경유지를 고려했을 때 f -> t의 최소 거리를 찾아보자.

 

이 경우에도 경유지 b를 실제로 경유했을 때와 b를 경유하지 않을 때로 나뉜다. b를 경유하지 않았던 상황은 사실 a까지만 고려한 상황(D[a](f, t))으로 이전의 작은 문제에서 풀었던 내용이다. b를 경유하는 상황에서 b는 도착점 또는 출발점임으로 경유지가 될 수 없고 다시 이전 상태인 a까지만 경유지로 고려했을 때 구할 수 있는 값들이다.따라서 a까지의 경유지를 고려한 상황에서 f에서 b가 목적지였던 상황(D[a](f, b)) + b에서 출발해서 t가 목적지인 상황의 비용(D[a](b, t))을 합한 것이다. 

역시 이 두 상황의 값 중 최소값이 D[b](t, f)가 된다.

이제 위 내용을 일반화 시켜 점화식을 구해보자.

 

이처럼 D[k](f, t)는 이전항인 D[k-1](f, t)의 관계에서 구해볼 수 있게 된다. 따라서 k 값의 변화에 따라 두 쌍의 정점(f, k), (k, t)의 비용을 하나씩 점검해보면 된다.

 

전개 과정

플로이드를 처리하기 위해서는 먼저 [추가로 알 수 있는 사항들]에 정의된 내용으로 그래프를 작성한다. 즉 정점 자신으로 가는 비용은 0, 연결된 간선의 비용은 간선 비용으로 업데이트 하고 나머지 현재 상태에서 연결되지 않은 정점들의 비용은 무한대로 설정해준다.

 

 

이제 각각의 정점들까지를 경유지로 설정했을 때 업데이트 가능한 지점들의 비용을 업데이트 해주자. 

먼저 1번 정점이 경유지로 들어가는 상황이다. 경유지는 출발점, 도착점이 될 수 없는데 1번 정점은 출발만 가능하기 때문에 업데이트 되는 내용이 없다.

이제 2번 정점까지를 경유지로 고려했을 때 업데이트 가능한 지점을 업데이트 해보면 다음과 같다.

 

 

다음은 3번 정점까지를 경유지로 고려했을 때 업데이트 가능한 지점을 업데이트 해보자.

 

 

다음은 4번 정점까지를 경유지로 고려했을 때 업데이트 가능한 지점을 업데이트 해보자.

 

다음으로 5번 정점까지를 경유지로 고려했을 때 상황이다.

 

5번이 추가되면서 6으로 가는 경로들이 뚤렸지만 앞에서 고려했던 3->4를 통해서 가는 비용이 훨씬 저렴하므로 업데이트 되는 내용은 없다.

 

다음으로 6번 정점까지를 고려했을 때의 상황이다.

마지막으로 7번 정점까지 고려했을 때의 상황인데 7번 정점은 목적지일 수밖에 없기 때문에 변경되는 내용은 없을 것이다.

 

알고리즘 구현

 

알고리즘 구현

플로이드 워셜의 구현은 다른 최단거리에 비해 매우 매우 간단하다.

graph = new int[V+1][V+1];

// 그래프 초기화: 자기 자신은 0, 연결 안된 경우 INF
for (int r = 1; r <= V; r++) {
    for (int c = 1; c <= V; c++) {
        graph[r][c] = r==c ? 0: INF;
    }
}

// 직접 간선 업데이트
for(int m=0; m<E; m++) {
    tokens = new StringTokenizer(input.readLine());
    int f = Integer.parseInt(tokens.nextToken());
    int t = Integer.parseInt(tokens.nextToken());
    int w = Integer.parseInt(tokens.nextToken());
    graph[f][t]=w;
}

// 모든 경유지(v)에서 발생할 수 있는 모든 정점의 쌍(f, t), (t, f)에 대한 점검
for (int v = 1; v <= V; v++) {
    for (int f = 1; f <= V; f++) {
        if(graph[f][v]==INF) { // f-v가 연결 안되어있으면 의미 없음
            continue;
        }
        for (int t = 1; t <= V; t++) { // v-t가 연결되어있고 경유한 비용이 더 작으면 업데이트
            if (graph[v][t]!=INF && graph[f][t] > graph[f][v] + graph[v][t]) {
                graph[f][t] = graph[f][v] + graph[v][t];
            }
        }
    }
}

 

시간 복잡도

플로이드 워셜은 모든 정점에 대한 경유지-출발점-도착점의 3중 반복문에 지배되므로 O(V^3)이다. 따라서 정점이 많은 경우는 문제가 될 수 있다.