Algorithm in A..Z - Floyd Warshall

개념

Floyd Warshall (플로이드 와샬) 알고리즘은 정점과 정점 사이의 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 특징은 모든 정점 사이의 거리를 구할 수 있다.

최단 경로를 찾을 때 중간에 한번 거쳐서 가는 경로 중 가장 가까운 경로로 업데이트 하면서 모든 정검들의 최단 거리를 구하는 알고리즘이다.

 

시간 복잡도가 O(V^3)이라는 꽤 오래 걸리는 알고리즘 이지만 모든 정점 사이의 최단 거리를 구할 수 있다.

---

작동원리

1. 중간 정점 K, 시작 정점 I, 도착 정점 J로 삼중 반복문을 순회한다.

2. distance[i][j]가 distance[i][k] + distance[k][j]보다 크면 경로를 업데이트 한다.

-> distance[i][k], distance[k][j]가 유효한 경로인지 체크해야 한다.

---

시간 복잡도

1. 반복문 순회 O(V^3)

 

O(V^3)

---

문제

https://www.acmicpc.net/problem/1956

1956번: 운동

---

코드

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> distance(n + 1, vector<int>(n + 1, INT32_MAX));
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;

        distance[u][v] = w;
    }

    for (int k = 1; k <= n; ++k) {
        for (int u = 1;u <= n;++u) {
            for (int v = 1;v <= n;++v) {
                if (distance[u][k] != INT32_MAX && distance[k][v] != INT32_MAX) {
                    distance[u][v] = min(distance[u][v], distance[u][k] + distance[k][v]);
                }
            }
        }
    }

    int answer = INT32_MAX;
    for (int i = 1;i <= n;++i) {
        if (distance[i][i] != INT32_MAX) {
            answer = min(answer, distance[i][i]);
        }
    }

    cout << (answer == INT32_MAX ? -1 : answer) << "\n";
}