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

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

시간 복잡도 : O(V^3) (V : 노드 수)

모든 노드 간 최단 경로를 탐색하는 알고리즘이다.
시간 복잡도가 크기 때문에, 보통 NODE가 100~200 정도이다. N=1000 정도라면 다른 알고리즘을 생각해볼 법한데, 1000^3번의 연산은 시간초과가 발생할 여지가 충분하기 때문이다.

ex) 플로이드-워셜 알고리즘 예제(백준 11404)

경유지 K를 가장 바깥 FOR문으로 두고,

그 내부 FOR문을 출발노드 START, 그 내부의 FOR문을 도착 노드 END에 관하여 둔다.

연결이 가능하다면(if문으로 무한대 값을 지녔는지 검사) k를 거쳐가는 경우가 최소 거리인지, k를 거치지 않는 경우가 최소 거리가 되는지를 연산하여 업데이트 한다.

나머지 설명은 코드 내부 주석 참고

#include <algorithm>
#include <iostream>
#include <vector>

#define D_SIZE 101
#define INF 2147000000

using namespace std;
int n, m;

vector<vector<int>> d(D_SIZE, vector<int>(D_SIZE, 0));
//int d[101][101];

void floyd_warshall() {
    // 가장 바깥에 거쳐가는 k를 둔다.
    for (int k = 1; k <= n; k++) {
        for (int s = 1; s <= n; s++) {
            for (int e = 1; e <= n; e++) {
                if (d[s][k] != INF && d[k][e] != INF) {
                    // k를 거쳐간 애가 지금의 d[s][e]보다 작으면 업데이트한다.
                    d[s][e] = min(d[s][e], d[s][k] + d[k][e]);
                }
            }
        }
    }
}

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

    // 모든 부분 무한대로 초기화, 자기 자신으로 가는 부분은 0으로 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                d[i][j] = 0;
            }
            else {
                d[i][j] = INF;
            }
        }

    }


    // 직접적으로 연결되어 있는 경우 입력 받아서 연결, 안되어있으면 INF 유지
    for (int i = 1; i <= m; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        d[start][end] = min(d[start][end], cost);
    }

    floyd_warshall();

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

    }


    return 0;
}