11-3. [C/C++] Floyd의 최단 경로 알고리즘

Floyd의 최단 경로 알고리즘

Floyd-Warshall 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 찾는 알고리즘이다.

다익스트라 알고리즘은 출발점이 정해져 있던 것과 달리 플로이드-워셜 알고리즘은 출발점이 정해져 있지 않다.

 

플로이드 워셜 알고리즘도 다익스트라처럼 단계마다 거쳐 가는 정점을 기준으로 알고리즘을 수행한다.

하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라 알고리즘과 다르다.

 

노드의 개수가 N개 일 때 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N²)의 연산을 통해

현재 노드를 거쳐 가는 모든 경로를 고려한다. 그래서 총 시간 복잡도는 O(N³)이 된다.

 

플로이드 워셜 알고리즘에서는 모든 노드에 대해 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 2차원 배열을 사용하므로 단계마다 O(N²)의 연산이 소요되는 것이다.

 

플로이드 워셜 알고리즘은 다이나믹 프로그래밍을 사용한다.

노드의 개수가 N개일 때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신하기 때문에 다이나믹 프로그래밍으로 분류한다.

플로이드 워셜 알고리즘의 점화식은 다음과 같다.

D_ab = min(D_ab , D_ak + D_kb)

D_ab은 정점 a에서 b로 가는 최단 거리를 의미한다.

이 점화식을 풀어서 얘기하자면 한 정점에서 어떤 정점으로 이동할 때 두 정점을 잇는 간선으로 한번에 가는 경우와 다른 정점을 통해 돌아서 가는 경우 중에서 더 빠른 길을 선택하겠다는 의미이다.

위 그림으로 플로이드 워셜 알고리즘의 과정을 따라가보자.

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 달리 시작 정점이 정해져 있지 않다.

두 정점이 직접적으로 연결되어 있지 않다면 INF 값을 저장해 연결되어 있지 않음을 명시한다.

 

매 단계마다 어떤 과정을 거치는 지 알아보자.

 

첫 번째 단계에서는 1번 노드를 거쳐 가는 경우를 구한다.

D₂₃ = min(D₂₃ , D₂₁ + D₁₃)

D₂₄ = min(D₂₄ , D₂₁ + D₁₄)

D₃₂ = min(D₃₂ , D₃₁ + D₁₂)

D₃₄ = min(D₃₄ , D₃₁ + D₁₄)

D₄₂ = min(D₄₂ , D₄₁ + D₁₂)

D₄₃ = min(D₄₃ , D₄₁ + D₁₃)

위 6가지 경우를 검사해 우변의 두 항 중에서 작은 값으로 갱신한다.

두 번째 단계에서는 2번 노드를 거쳐 가는 경우를 구한다. (점화식은 생략)

세 번째 단계에서는 3번 노드를 거쳐 가는 경우를 구한다.

노드의 개수가 4개 이므로 이번이 마지막 단계이다.

이때는 4번 노드를 거쳐 가는 경우를 구한다.

모든 노드에 대해 해당 노드를 거쳐 가는 경우를 고려했다면 최종 테이블이 나온다.

---

코드로 구현

11404번: 플로이드

#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
#define INF 1e9
#define SIZE 101

int N, M;
int graph[SIZE][SIZE];

void initInput() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i != j) graph[i][j] = INF;
        }
    }
    for (int i = 0; i < M; i++) {
        int v1, v2, weight;
        cin >> v1 >> v2 >> weight;
        graph[v1][v2] = min(graph[v1][v2], weight);
    }
}

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

void solve() {
    floyd();

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (graph[i][j] == INF) cout << 0 << ' ';
            else cout << graph[i][j] << ' ';
        }
        cout << endl;
    }
}

int main(void)
{
    cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
    initInput();
    solve();

    return 0;
}