BOJ 11404 - 플로이드

BOJ 11404 - 플로이드

“플로이드-워셜 알고리즘”

BOJ 11404 - 플로이드

문제 링크


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

const int INF = 0x3f3f3f3f;
int ans[110][110];
bool vis[110];
int n, m;

void    Floyd()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (ans[j][k] > ans[j][i] + ans[i][k])
                    ans[j][k] = ans[j][i] + ans[i][k];
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (i != j)
                ans[i][j] = INF;
    }
    
    for (int i = 0; i < m; i++) {
        int p, c, m; cin>>p>>c>>m;
        if (ans[p][c] == 0) 
            ans[p][c] = m;
        else 
            ans[p][c] = min(m, ans[p][c]);
    }

    Floyd();

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

  • 플로이드-워셜 알고리즘을 사용하여 주어진 그래프에서 모든 정점 쌍 사이의 최단 거리를 구하고 출력하는 문제이다. 방향 그래프이든 무방향 그래프이든 상관없고, 간선이 음수여도 동작하지만 음의 사이클이 존재할 경우 문제가 생길 수 있다.

  • 자세한 구현법은 아래 참고.

[실전 알고리즘] 0x1C강 - 플로이드 알고리즘

  • 플로이드 알고리즘은 다익스트라 알고리즘에 비해 구현이 간편하여, 3중 for문을 도는 것으로 간편하게 구현할 수 있다.
void    Floyd()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                // i가 사이 노드, j가 시작 노드, k가 도착 노드이다.
                if (ans[j][k] > ans[j][i] + ans[i][k])
                    ans[j][k] = ans[j][i] + ans[i][k];
                // j에서 k까지의 거리가, i를 거쳐서 가는 거리보다 짧으면
                // 거리를 갱신해준다.
            }
        }
    }
}
  • 따라서 O(V^3)의 시간복잡도로 모든 정점 쌍에 사이의 최단거리를 구해낼 수가 있다. 이게 어떻게 가능한지 증명할 수는 있다고 하던데, 그것까지는 따로 공부하지 않으려 한다…