[알고리즘 공부] 플로이드 워셜

0. 개요

요즘 막학기가 종강하고 조금 해이해진 것 같다...

이제 진짜 백수 신분이기 때문에 더 힘내서 공부해보려고 한다!!

 

1. 알고리즘 개념

플로이드 워셜 알고리즘은 모든 정점 간의 최단 거리를 구할 때 사용되는 알고리즘으로,

다이나믹 프로그래밍(DP) 기법 중 하나이다.

정점 A에서 정점 B로 이동할 때, 정점 K를 거쳐가는 것이 더 유리한가? 를 계산하는 알고리즘으로 볼 수 있다.

 

이 역시 이전 시간에 정리해보았던 벨만 포트 알고리즘과 유사하게

음수 가중치가 있는 그래프에서도 사용될 수 있지만,

음수 사이클이 있을 경우 사용될 수 없다.

또한 이 역시 모든 경우의 수를 모두 탐색하기에 정점 수가 적은 경우에 사용될 수 있다.

 

2. 알고리즘 구현

플로이드 워셜 알고리즘은 위에서 말했던 것처럼

k 번째 정점을 거쳐갔을 때의 최단거리를 구하는 것임으로 

모든 정점을 순회해야한다.

 

다음은 예시 구현 내용이다.

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    const int MAX = INT16_MAX;
    vector<vector<int>> dist(N + 1, vector<int>(N + 1, MAX));

    // 간선 초기화
    for (int i = 1; i <= N; i++) 
        dist[i][i] = 0;

    // 간선 값 입력(방향 그래프 기준)
    for (int i = 0; i < M; i++) {
        int a, b;
        int w;
        cin >> a >> b >> w;
        dist[a][b] = min(dist[a][b], w);
    }

    // 최단 거리 검색
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {

            // dist[i][k]가 MAX면 어차피 최단 거리가 아님
            if (dist[i][k] == MAX) 
                continue;

            for (int j = 1; j <= N; j++) {
                
                if (dist[k][j] == MAX) 
                    continue;

                int t = dist[i][k] + dist[k][j];
                if (t < dist[i][j]) 
                    dist[i][j] = t;
            }
        }
    }

    // 음수 사이클 검색 (거리가 0보다 적으면 음수 사이클)
    bool hasNegCycle = false;
    for (int i = 1; i <= N; i++) {
        if (dist[i][i] < 0) {
            hasNegCycle = true;
            break;
        }
    }
    if (hasNegCycle) {
        cout << "음수 사이클 탐지\n";
        return 0;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (dist[i][j] == MAX) cout << 0 << ' ';
            else cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}