[Algorithm] 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

 

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 벨만포드 알고리즘과는 다르게 모든 정점사이의 최단 경로를 한 번에 구하는 알고리즘 입니다. 다익스트라와 벨만포드 알고리즘도 정점의 갯수번 만큼 돌리게 되면 모두 구할 수 있습니다.

 

 

- 플로이드 워셜 알고리즘

 

 기본적인 아이디어는 A->B로 가는 경로는 A->K->B(K는 경유지) K라는 경유지를 거쳐서 무조건 가게 된다는 생각이다. K는 그래프 상에 존재하는 모든 정점이 될 수 있다.

 

궁극적으로 A에서 K라는 경유지를 거쳐 B로 갈 수 있는 최단 거리를 구하는 것이다.

 

D[i][j] 를 i에서 출발해 j까지 가는 최단 거리라고 했을 때, 다음 점화식을 만족한다.

 

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

 

 

 

 

https://www.acmicpc.net/problem/11404 (플로이드) 

 

플로이드 워셜 알고리즘의 기본 문제이다. 구현도 간단하여 따로 설명은 생략하겠습니다.

 

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, m;
int f[101][101];
 
int main() {
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) f[i][j] = 0;
            else { f[i][j] = 987654321; }
        }
    }
 
 
    for (int i = 0; i < m; i++) {
        int A, B, C; 
        cin >> A >> B >> C;
        
        if (f[A][B] > C) {
            f[A][B] = C;
        }
    }
 
    
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }    
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (f[i][j] == 987654321) {
                cout << 0 << ' ';
            }
            else {
                cout << f[i][j] << ' ';
            }
        }
        cout << '\n';
    }
 
    return 0;
 
 
}