플로이드 워셜 (Floyd Warshall)

이번에는 최단 경로 알고리즘 중 하나인 플로이드 워셜에 대해서 공부해보자.

모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해주는 알고리즘에 대해서 배워보자.

플로이드 워셜

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해주는 알고리즘이다.

 

쉽게 설명하면, A 노드에서 B 노드로 가는 최단 경로가

A -> B (한 번에 가는 것)

A -> K -> B (어떤 노드를 거쳐서 가는 것)

가 있을 텐데 이중 우리는 더 짧은 경로를 원하므로 min(A -> B, A -> K -> B)를 갱신하면 된다.

 

단계마다 거쳐 가는 노드를 기준으로 더 짧은 경로를 선택하며 반복하는 것이다.

이때 단계마다 비용이 O(N^2)이다.

거쳐 가는 노드를 기준으로 시작 노드에서 도착 노드까지 모든 경로를 검사하는데 드는 비용이 N^2 이므로

거쳐 가는 노드가 N개이면? 시간 복잡도는 O(N x N^2) = O(N^3)

 

플로이드 워셜 알고리즘은 다이나믹 프로그래밍의 기법이기도 하다.

점화식을 살펴보면 D[a][b] = min(D[a][b], D[a][k] + D[k][b])

구현 방법

플로이드 워셜은 사전 작업이 필요하다.

• 2차원 배열을 무한 값으로 초기화
• 자기 자신에서 자기 자신으로 가는 비용은 0으로 갱신
• 이후 간선의 정보를 입력받고 플로이드 워셜을 수행

//플로이드 워셜
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int n, m;
int graph[501][501];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    //최단 거리 테이블을 모두 무한으로 초기화
    fill(graph[0], graph[0] + 501 * 501, INF);
    
    //자기 자신으로 가는 비용은 0으로
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) graph[i][j] = 0;
        }
    }
    
    //각 간선에 대한 정보를 입력 받아 그 값으로 초기화
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
    }
    
    //점화식에 따라 플로이드 워셜 알고리즘 수행
    //D[a][b] = min(D[a][b], D[a][k] + D[k][b])
    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]);
            }
        }
    }
    
    //그래프 출력
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(graph[i][j] == INF)
                cout << "INF\n";
            else
                cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

연습문제

플로이드

역사

회장뽑기

운동

플로이드2

경로찾기