플로이드-워셜 알고리즘 |BLOG.INJUN.DEV

플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프의 모든 정점 쌍(All-Pairs) 사이의 최단 경로를 찾는 동적 프로그래밍 기반 알고리즘으로, 1962년 Robert Floyd와 Stephen Warshall에 의해 독립적으로 발표되었으며, 다익스트라나 벨만-포드 알고리즘과 달리 한 번의 실행으로 모든 쌍의 최단 경로를 동시에 계산한다는 특징을 가진다. O(V³)의 시간 복잡도를 가지며 음수 가중치를 가진 간선을 처리할 수 있고 음수 사이클의 존재 여부도 탐지할 수 있어, 네트워크 지름 계산, 추이적 폐쇄 연산, 데이터베이스 쿼리 최적화 등 다양한 분야에서 핵심적으로 활용되고 있다.

플로이드-워셜 알고리즘의 역사

플로이드-워셜 알고리즘이란?
가중치가 있는 그래프에서 모든 정점 쌍 사이의 최단 경로를 동시에 찾는 동적 프로그래밍 기반 알고리즘으로, 음수 가중치 간선을 처리할 수 있고 음수 사이클의 존재 여부를 탐지할 수 있다.

플로이드-워셜 알고리즘은 1962년 미국의 컴퓨터 과학자 Robert W. Floyd가 Communications of the ACM 저널에 발표한 논문 “Algorithm 97: Shortest Path"에서 최단 경로 문제에 적용한 형태로 제시되었으며, 같은 해 Stephen Warshall이 Journal of the ACM에 발표한 논문 “A Theorem on Boolean Matrices"에서 추이적 폐쇄(Transitive Closure) 문제에 적용한 형태로 독립적으로 발표되었다. 두 연구자의 이름을 따서 플로이드-워셜 알고리즘이라고 명명되었으나, 흥미롭게도 프랑스의 수학자 Bernard Roy가 1959년에 발표한 연구에서 이미 본질적으로 동일한 알고리즘을 기술했기 때문에 일부 유럽 문헌에서는 “Roy-Floyd-Warshall 알고리즘"이라고 부르기도 한다.

이 알고리즘은 동적 프로그래밍의 고전적인 예시로 컴퓨터 과학 교육에서 자주 다루어지며, 그래프 이론과 최적화 이론의 발전에 중요한 기여를 했다. Robert Floyd는 이 알고리즘을 포함한 프로그래밍 언어와 알고리즘 분야의 공헌으로 1978년 튜링 상을 수상했다. 현대 컴퓨터 과학에서 이 알고리즘은 네트워크 라우팅, 게임 이론의 도달 가능성 분석, 데이터베이스의 관계 연산, 소셜 네트워크의 연결성 분석 등 다양한 분야에서 실용적으로 활용되고 있다.

알고리즘의 동작 원리

플로이드-워셜 알고리즘의 핵심 아이디어는 “중간 정점(Intermediate Vertex)“의 개념으로, 정점 집합 {1, 2, …, k}만을 중간 정점으로 사용하여 i에서 j로 가는 최단 경로를 점진적으로 계산한다.

동적 프로그래밍 점화식

핵심 점화식
D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])
정점 1부터 k까지를 중간 정점으로 사용할 수 있을 때, i에서 j로 가는 최단 거리는 (1) k를 거치지 않는 경로와 (2) k를 거치는 경로 중 더 짧은 것이다.

실제 구현에서는 공간 최적화를 위해 3차원 배열 대신 2차원 배열을 사용하며, 이는 k번째 단계에서 D[i][k]와 D[k][j] 값이 k를 중간 정점으로 사용하지 않는 경로의 값과 동일하기 때문에 안전하게 수행할 수 있다.

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

이 점화식은 “정점 k를 경유하는 것이 더 짧으면 갱신한다"는 의미를 담고 있으며, 이는 최단 경로의 부분 경로도 최단 경로라는 최적 부분 구조(Optimal Substructure) 성질을 활용한 것이다.

3중 루프의 의미

알고리즘의 구조는 세 개의 중첩된 루프로 구성되며, 각 루프의 역할과 순서가 정확성에 매우 중요하다.

가장 바깥 루프 (k): 중간 정점을 1부터 V까지 순차적으로 선택한다. k번째 반복에서는 정점 {1, 2, …, k}만을 중간 정점으로 고려하며, k가 증가할수록 더 많은 중간 정점을 사용하는 경로를 탐색하여 점진적으로 최적해에 도달한다.

중간 루프 (i): 시작 정점을 1부터 V까지 순회한다.

가장 안쪽 루프 (j): 도착 정점을 1부터 V까지 순회한다.

루프의 순서가 k → i → j인 것이 핵심이며, 만약 k가 가장 안쪽에 있으면 알고리즘이 올바르게 동작하지 않는다. k가 가장 바깥에 있어야 k번째 단계에서 k-1번째까지의 결과를 사용하는 동적 프로그래밍의 점진적 확장이 보장된다.

알고리즘 수행 단계

1단계: 초기화

V × V 크기의 2차원 배열 D를 생성하고, 인접한 정점 사이는 간선의 가중치로 초기화하며, 연결되지 않은 정점 사이는 무한대(INF)로 설정하고, 자기 자신으로의 거리 D[i][i]는 0으로 설정한다.

2단계: 3중 루프 실행

중간 정점 k를 1부터 V까지 순회하면서, 모든 (i, j) 쌍에 대해 D[i][j] = min(D[i][j], D[i][k] + D[k][j])를 적용한다.

3단계: 결과 확인

알고리즘 종료 후 D[i][j]는 정점 i에서 정점 j로 가는 최단 거리를 담고 있으며, 만약 음수 사이클이 존재하면 대각선 원소 중 D[i][i] < 0인 경우가 발생한다.

동작 예시

다음과 같은 그래프가 있다고 가정한다.

정점: 1, 2, 3, 4
간선: 1→2(3), 1→3(8), 1→4(∞), 2→3(2), 2→4(5), 3→4(1)

초기 거리 행렬:

    1    2    3    4
1 [ 0    3    8    ∞  ]
2 [ ∞    0    2    5  ]
3 [ ∞    ∞    0    1  ]
4 [ ∞    ∞    ∞    0  ]

k=1 후 (정점 1을 중간 정점으로 고려): 변화 없음

k=2 후 (정점 1, 2를 중간 정점으로 고려):

D[1][3] = min(8, 3+2) = 5 (1→2→3)
D[1][4] = min(∞, 3+5) = 8 (1→2→4)

k=3 후 (정점 1, 2, 3을 중간 정점으로 고려):

D[1][4] = min(8, 5+1) = 6 (1→2→3→4)
D[2][4] = min(5, 2+1) = 3 (2→3→4)

최종 결과:

    1    2    3    4
1 [ 0    3    5    6  ]
2 [ ∞    0    2    3  ]
3 [ ∞    ∞    0    1  ]
4 [ ∞    ∞    ∞    0  ]

구현 예제

플로이드-워셜 알고리즘의 C++ 구현이다.

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

int main() {
    int n, m; // n: 정점 수, m: 간선 수
    cin >> n >> m;

    // 거리 행렬 초기화
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));

    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0; // 자기 자신으로의 거리는 0
    }

    // 간선 입력
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], (long long)c); // 중복 간선 처리
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 음수 사이클 검사
    bool hasNegativeCycle = false;
    for (int i = 1; i <= n; i++) {
        if (dist[i][i] < 0) {
            hasNegativeCycle = true;
            break;
        }
    }

    if (hasNegativeCycle) {
        cout << "음수 사이클이 존재합니다." << '\n';
    } else {
        // 결과 출력
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == INF) {
                    cout << "INF ";
                } else {
                    cout << dist[i][j] << ' ';
                }
            }
            cout << '\n';
        }
    }

    return 0;
}

코드 설명

dist: V × V 크기의 2차원 배열로, dist[i][j]는 정점 i에서 j로 가는 최단 거리를 저장한다.
dist[i][i] = 0: 자기 자신으로의 거리는 항상 0으로 초기화해야 하며, 이를 빠뜨리면 잘못된 결과가 나온다.
dist[i][k] != INF && dist[k][j] != INF 조건: 오버플로우를 방지하기 위해 INF와의 덧셈을 수행하기 전에 검사한다.
중복 간선 처리: 같은 (a, b) 쌍에 여러 간선이 주어질 수 있으므로 최솟값을 선택한다.

음수 가중치와 음수 사이클

플로이드-워셜 알고리즘은 다익스트라 알고리즘과 달리 음수 가중치를 가진 간선을 올바르게 처리할 수 있으며, 이는 동적 프로그래밍 특성상 모든 가능한 경로를 체계적으로 탐색하기 때문이다.

음수 사이클의 의미

음수 사이클이란?
사이클을 구성하는 간선들의 가중치 합이 음수인 사이클로, 음수 사이클이 존재하면 그 사이클을 무한히 반복함으로써 거리를 음의 무한대로 줄일 수 있어 최단 경로가 정의되지 않는다.

예를 들어 A → B → C → A로 돌아오는 경로의 가중치 합이 -5라면, 이 사이클을 반복할수록 거리가 -5, -10, -15, …로 계속 감소한다. 따라서 음수 사이클에 포함된 정점과 그 정점에서 도달할 수 있는 모든 정점 쌍의 최단 거리는 음의 무한대가 된다.

음수 사이클 탐지 방법

플로이드-워셜 알고리즘 실행 후 대각선 원소를 검사하여 음수 사이클을 O(V) 시간에 탐지할 수 있다. 정상적인 경우 자기 자신으로 돌아오는 최단 거리 D[i][i]는 항상 0이어야 하지만, 음수 사이클이 존재하면 D[i][i] < 0인 정점이 발견된다. 이 정점 i는 음수 사이클에 포함되어 있거나 음수 사이클에 도달할 수 있는 정점이다.

음수 사이클의 실제 응용

금융 거래에서 차익 거래(Arbitrage) 탐지에 음수 사이클이 활용된다. 여러 화폐 간의 환율을 그래프로 모델링할 때, 환율 r을 -log(r)로 변환하면 환전 과정의 곱셈이 덧셈으로 바뀌며, 음수 사이클이 존재하면 환전을 반복하여 무위험 수익을 얻을 수 있는 차익 거래 기회가 존재함을 의미한다.

시간 복잡도 분석

플로이드-워셜 알고리즘의 시간 복잡도는 O(V³)이며, 여기서 V는 정점의 개수이다.

O(V³) 상세 분석

3중 반복문의 각 루프가 V번씩 실행되므로 총 V × V × V = V³번의 비교 및 갱신 연산이 수행되며, 각 연산은 덧셈, 비교, 최솟값 선택으로 구성되어 상수 시간 O(1)에 수행된다. 공간 복잡도는 O(V²)로, V × V 크기의 2차원 배열이 필요하며, 경로 복원을 위해 next 배열을 추가하더라도 여전히 O(V²)이다.

실용적인 한계

정점 수 (V)	연산 횟수	예상 실행 시간
100	10⁶	< 0.01초
500	1.25 × 10⁸	약 0.5초
1,000	10⁹	약 5초
5,000	1.25 × 10¹¹	실용적이지 않음

현대 컴퓨터에서 V가 500 정도까지는 1초 이내에 처리 가능하며, V가 1,000을 넘어가면 실행 시간이 급격히 증가하여 대규모 그래프에서는 다른 알고리즘을 고려해야 한다.

다른 최단 경로 알고리즘과의 비교

비교 항목	플로이드-워셜	다익스트라 (V번 실행)	벨만-포드 (V번 실행)
시간 복잡도	O(V³)	O(VE log V)	O(V²E)
희소 그래프 (E ≈ V)	O(V³)	O(V² log V)	O(V³)
밀집 그래프 (E ≈ V²)	O(V³)	O(V³ log V)	O(V⁴)
음수 가중치	지원	미지원	지원
음수 사이클 탐지	가능	불가	가능
구현 복잡도	매우 간단	중간	간단

알고리즘 선택 가이드

모든 쌍 최단 경로, 밀집 그래프: 플로이드-워셜 알고리즘
모든 쌍 최단 경로, 희소 그래프, 양수 가중치만: 다익스트라 V번 실행
단일 시작점 최단 경로: 다익스트라 또는 벨만-포드
음수 가중치, 음수 사이클 탐지 필요: 플로이드-워셜 또는 벨만-포드
구현 간단함 중시, 정점 수 적음: 플로이드-워셜 알고리즘

경로 복원

최단 거리뿐만 아니라 실제 경로를 복원해야 하는 경우가 많으며, 이를 위해 next 배열을 사용한다.

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

void printPath(int i, int j, vector<vector<int>>& next) {
    if (next[i][j] == -1) {
        cout << "경로 없음" << '\n';
        return;
    }

    cout << i;
    while (i != j) {
        i = next[i][j];
        cout << " -> " << i;
    }
    cout << '\n';
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> next(n + 1, vector<int>(n + 1, -1));

    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c < dist[a][b]) {
            dist[a][b] = c;
            next[a][b] = b; // 직접 연결된 정점으로 초기화
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k]; // i에서 j로 갈 때 첫 번째로 방문할 정점
                }
            }
        }
    }

    // 1에서 n으로 가는 경로 출력
    printPath(1, n, next);

    return 0;
}

next[i][j]는 정점 i에서 j로 가는 최단 경로에서 i 바로 다음에 방문하는 정점을 저장하며, 거리를 갱신할 때마다 next도 함께 갱신한다. 경로를 출력할 때는 next를 따라가며 모든 중간 정점을 순차적으로 나열한다.

실제 응용 사례

플로이드-워셜 알고리즘은 다양한 실제 문제에서 핵심적으로 활용된다.

추이적 폐쇄(Transitive Closure)

추이적 폐쇄는 그래프에서 정점 i에서 정점 j로 “도달 가능한지"를 판단하는 문제로, 가중치를 무시하고 연결 여부만 확인한다. 플로이드-워셜의 변형인 Warshall 알고리즘은 boolean 연산을 사용하여 이 문제를 해결하며, 데이터베이스의 관계 분석(예: “A는 B의 조상인가?”), 프로그램 분석의 제어 흐름 도달 가능성, 컴파일러 최적화 등에 활용된다.

네트워크 지름(Network Diameter) 계산

모든 정점 쌍의 최단 거리 중 최댓값이 네트워크의 지름(Diameter)이며, 이는 네트워크의 효율성과 취약점을 평가하는 핵심 지표이다. 통신 네트워크에서 최악의 전송 지연 시간을 나타내며, 소셜 네트워크 분석에서 “가장 멀리 떨어진 두 사람” 사이의 거리(예: Six Degrees of Separation)를 계산하는 데 사용된다.

도시 간 교통망 최적화

모든 도시 쌍 사이의 최단 경로를 사전에 계산하여 물류 센터 배치, 교통 인프라 투자 우선순위 결정, 긴급 서비스 배치 최적화 등에 활용된다. 정점 수가 제한된 소규모 네트워크에서는 플로이드-워셜로 모든 경로를 미리 계산하고 쿼리에 O(1) 시간으로 응답할 수 있다.

게임 AI 경로 탐색

게임 맵이 충분히 작은 경우(예: 격자 기반 전략 게임의 섹터), 모든 쌍의 최단 경로를 사전 계산해두면 런타임에 빠르게 경로를 찾을 수 있다. 이는 A* 알고리즘을 매번 실행하는 것보다 응답 시간이 훨씬 빠르며, 메모리 제약이 허용하는 경우 효과적인 최적화 전략이다.

최적화 기법

공간 최적화

3차원 배열 D[k][i][j] 대신 2차원 배열 D[i][j]를 재사용하여 공간을 O(V³)에서 O(V²)로 줄일 수 있으며, 이는 k번째 단계에서 D[i][k]와 D[k][j]가 k-1번째 결과와 동일하기 때문에 안전하다.

병렬 처리

각 k 단계에서 모든 (i, j) 쌍에 대한 갱신은 서로 독립적이므로 병렬화할 수 있다. GPU나 멀티코어 CPU를 활용하면 내부 두 개의 루프를 병렬로 처리하여 큰 속도 향상을 얻을 수 있으며, 대규모 그래프에서 실용적인 성능을 달성하는 데 중요한 기법이다.

조기 종료

특정 k 단계에서 어떤 거리도 갱신되지 않으면 이후 단계에서도 갱신이 발생하지 않으므로 종료할 수 있다. 하지만 이 검사 자체에 O(V²)의 비용이 들어 항상 유리한 것은 아니며, 실제로는 그래프의 특성에 따라 효과가 다르다.

구현 시 주의사항

INF 값 선택: INF + INF가 오버플로우하지 않도록 충분히 크면서도 여유가 있는 값을 선택해야 하며, int 범위에서는 1e9, long long 범위에서는 1e18/2 정도가 적당하다.
자기 자신 거리 초기화: D[i][i] = 0을 빠뜨리면 잘못된 결과가 나오므로 반드시 초기화해야 한다.
중복 간선 처리: 같은 (a, b) 쌍에 여러 간선이 주어질 수 있으므로 최솟값을 선택해야 한다.
무향 그래프: 양방향 간선으로 표현하며 (a, b)와 (b, a) 모두 추가해야 한다.
경로 복원: 필요한 경우 처음부터 next 배열을 유지해야 하며, 나중에 추가하기 어렵다.

결론

플로이드-워셜 알고리즘은 1962년 Robert Floyd와 Stephen Warshall에 의해 독립적으로 발표된 알고리즘으로, 동적 프로그래밍의 원리를 활용하여 그래프의 모든 정점 쌍 사이의 최단 경로를 O(V³) 시간에 계산한다. 다익스트라나 벨만-포드와 달리 한 번의 실행으로 모든 쌍의 최단 경로를 동시에 얻을 수 있으며, 음수 가중치를 처리하고 음수 사이클을 탐지할 수 있다. 3중 루프와 한 줄의 갱신 로직만으로 구현되어 매우 간단하면서도 강력하며, 추이적 폐쇄, 네트워크 지름 계산, 교통망 최적화, 게임 AI 등 다양한 분야에서 핵심적으로 활용된다. 정점 수가 수백 개 이하인 밀집 그래프에서 모든 쌍의 최단 경로가 필요한 경우 가장 적합한 선택이다.

플로이드-워셜 알고리즘의 역사#

알고리즘의 동작 원리#

동적 프로그래밍 점화식#

3중 루프의 의미#

알고리즘 수행 단계#

동작 예시#

구현 예제#

코드 설명#

음수 가중치와 음수 사이클#

음수 사이클의 의미#

음수 사이클 탐지 방법#

음수 사이클의 실제 응용#

시간 복잡도 분석#

O(V³) 상세 분석#

실용적인 한계#

다른 최단 경로 알고리즘과의 비교#

알고리즘 선택 가이드#

경로 복원#

실제 응용 사례#

추이적 폐쇄(Transitive Closure)#

네트워크 지름(Network Diameter) 계산#

도시 간 교통망 최적화#

게임 AI 경로 탐색#

최적화 기법#

공간 최적화#

병렬 처리#

조기 종료#

구현 시 주의사항#

결론#