25. 플로이드 워셜

플로이드 워셜

빠른 설명

플로이드 워셜은 모든 정점 쌍 사이의 최단거리를 구하는 알고리즘이다. 중간 정점 $k$를 거쳐 가는 경우를 하나씩 허용하며 거리를 갱신한다.

언제 쓰는가

• 모든 정점 쌍의 최단거리가 필요할 때
• 정점 수가 작을 때
• 음수 간선은 있지만 음수 사이클은 없을 때

시간복잡도

• $O(V^3)$
• 메모리 $O(V^2)$

참고자료

• CP-Algorithms - Floyd-Warshall
• Wikipedia - Floyd-Warshall algorithm
• GeeksforGeeks - Floyd Warshall Algorithm
• 나무위키 - 플로이드-워셜 알고리즘

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
const int INF = 1e9;
 
int main() {
    int n = 4;
    vector<vector<int>> dist(n, vector<int>(n, INF));
 
    for (int i = 0; i < n; i++) dist[i][i] = 0;
 
    dist[0][1] = 3;
    dist[0][2] = 10;
    dist[1][2] = 2;
    dist[2][3] = 1;
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
 
    cout << dist[0][3] << '\n';
}

Python 코드

INF = 10**9
n = 4
dist = [[INF] * n for _ in range(n)]
 
for i in range(n):
    dist[i][i] = 0
 
dist[0][1] = 3
dist[0][2] = 10
dist[1][2] = 2
dist[2][3] = 1
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][k] == INF or dist[k][j] == INF:
                continue
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
print(dist[0][3])