Back to Blog
알고리즘플로이드Floyd최단거리경로복원

0x1C. 플로이드-워셜 - 모든 쌍 최단 경로

플로이드 알고리즘의 개념과 구현, 경로 복원 방법을 정리한다.

0x1C 플로이드

최단 거리 알고리즘 하면 보통 다익스트라(Dijkstra)를 먼저 떠올린다. 하지만 다익스트라는 하나의 출발점에서 나머지 정점까지의 최단 거리를 구하는 알고리즘이다. 만약 모든 정점 쌍 사이의 최단 거리가 필요하다면? 다익스트라를 N번 돌리는 방법도 있지만, 이럴 때 훨씬 간결하게 쓸 수 있는 알고리즘이 바로 플로이드(Floyd-Warshall) 알고리즘이다.

0x00 알고리즘 설명

플로이드 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다.

핵심 아이디어는 DP(동적 프로그래밍) 에 기반한다. 정점 i에서 j로 가는 최단 경로를 구할 때, 중간에 거쳐가는 정점 k를 하나씩 추가하면서 거리를 갱신하는 것이다. 즉, "i에서 j로 직접 가는 것"과 "i에서 k를 거쳐 j로 가는 것" 중 더 짧은 쪽을 선택한다. 이를 점화식으로 표현하면 다음과 같다.

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

이 갱신을 k = 1부터 N까지 모든 중간 정점에 대해 반복하면, 최종적으로 모든 정점 쌍의 최단 거리가 완성된다.

시간 복잡도는 3중 반복문을 사용하므로 O(N^3) 이다. 정점 수가 수백 개 이하일 때 적합하고, 정점이 수천 개를 넘어가면 느려지므로 다른 알고리즘을 고려해야 한다. 반면 구현이 매우 짧고 직관적이라는 장점이 있어, N이 작은 문제에서는 다익스트라보다 오히려 편리하다.

0x01 구현

기본적인 플로이드 구현은 놀라울 정도로 간단하다. 거리 배열 d[i][j]를 INF로 초기화한 뒤, 입력받은 간선 정보를 넣고, 3중 반복문 하나로 끝난다.

초기화 시 주의할 점이 두 가지 있다. 첫째, 자기 자신으로 가는 거리는 d[i][i] = 0으로 설정해야 한다. 둘째, 같은 간선이 여러 개 들어올 수 있으므로 min을 사용하여 가장 짧은 간선만 유지한다.

3중 반복문에서 k가 가장 바깥 루프에 온다는 점이 중요하다. k는 "중간에 거쳐가는 정점의 번호"를 의미하며, k를 1부터 N까지 순서대로 확장하면서 최단 거리를 갱신하는 것이 알고리즘의 핵심이다. i와 k의 루프 순서를 바꾸면 올바른 결과가 나오지 않는다.

출력 시에는 도달 불가능한 경우(값이 INF인 경우) 0으로 출력하도록 처리한다.

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int d[105][105];
int n, m;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        fill(d[i], d[i]+n, INF);
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }
    for(int i = 1; i <= n; i++) d[i][i]= 0;

    for(int k= 1; k <= n; k++)
        for(int i= 1; i <= n; i++)
            for(int j= 1; j <= n; j++)
                d[i][j]= min(d[i][j], d[i][k]+d[k][j]);

    for(int i= 1; i <= n; i++){
        for(int j= 1; j <= n; j++){
            if(d[i][j]= INF) cout << "0 ";
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

0x02 경로 복원 방법

최단 거리뿐 아니라 실제 경로까지 출력해야 하는 문제도 있다. 이때는 거리 배열 d 외에 경로 추적용 배열 nxt(또는 mat)를 하나 더 둔다.

nxt[i][j]는 "정점 i에서 j로 가는 최단 경로에서, i 다음에 방문하는 정점"을 저장한다. 초기값은 직접 연결된 간선이 있을 때 nxt[a][b] = b로 설정한다.

플로이드 갱신 과정에서 d[i][k] + d[k][j] < d[i][j]인 경우, 거리를 갱신하면서 동시에 nxt[i][j] = nxt[i][k]로 업데이트한다. i에서 j로 가는 최단 경로가 k를 거치게 되었으므로, i의 다음 정점은 "i에서 k로 가는 경로의 다음 정점"과 같아지기 때문이다.

경로를 복원할 때는 시작점 st = i에서 출발하여 st = nxt[st][j]를 반복하며 목적지 j에 도달할 때까지 따라가면 된다. 이렇게 하면 최단 경로 위의 모든 정점을 순서대로 얻을 수 있다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int d[105][105];
int mat[105][105];
int n, m;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        fill(d[i], d[i]+n+1, INF);

    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
        mat[a][b] = b;
    }

    for(int i = 1; i <= n; i++) d[i][i]= 0;

    for(int k= 1; k <= n; k++)
        for(int i= 1; i <= n; i++)
            for(int j= 1; j <= n; j++)
                if(d[i][k] + d[k][j] < d[i][j]){
                    d[i][j]= d[i][k]+d[k][j];
                    mat[i][j]= mat[i][k];
                }

    for(int i= 1; i <= n; i++){
        for(int j= 1; j <= n; j++){
            if(d[i][j]= INF) cout << "0 ";
            else cout << d[i][j] << " ";
        }
        cout << '\n';
    }

  for(int i= 1; i <= n; i++){
    for(int j= 1; j <= n; j++){
      if(d[i][j]= 0 || d[i][j]= INF){
        cout << "0\n";
        continue;
      }
      vector<int> path;
      int st = i;
      while(st != j){
        path.push_back(st);
        st = nxt[st][j];
      }
      path.push_back(j);
      cout << path.size() << " ";
      for(auto x : path) cout << x << " ";
      cout << "\n";
    }
  }
}

문제 풀이

관련 문제를 풀면서 추가 정리할 예정이다.

리뷰

플로이드는 구현 자체가 짧아서 외우기 쉽지만, DP의 관점에서 "k가 왜 바깥 루프여야 하는지"를 제대로 이해하는 것이 중요하다. 다익스트라가 하나의 출발점 기준이라면, 플로이드는 전체를 한 번에 처리한다는 점에서 용도가 명확히 다르다. N이 작을 때(보통 500 이하) 모든 쌍 최단 거리가 필요하면 플로이드를, 특정 출발점에서의 최단 거리가 필요하면 다익스트라를 선택하면 된다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편