(라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

그래프 거리 구하는 알고리즘 세번째! 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220797649276&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)

 

모든 간선을 다 확인하는 가장 비싸지만 가장 확실한 알고리즘으로 시간복잡도가 $O(V^3)$이다.

알고리즘은 매우 간단하다! 행렬을 고등학교때 배운 사람이라면 이미 아는 내용!!

 

라이님 풀이를 gpt에게 맡겨서 오버플로를 방지하고 불필요한 계산 결과를 덜어내보았다.

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    int dist[100][100];

    // 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INT_MAX;
        }
    }

    // 입력
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (dist[a - 1][b - 1] > c) {
            dist[a - 1][b - 1] = c;
        }
    }

    // Floyd-Warshall 알고리즘
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            if (dist[i][k] == INT_MAX) continue; // 중간 노드가 무한대면 건너뜀
            for (int j = 0; j < N; j++) {
                if (dist[k][j] != INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dist[i][j] == INT_MAX)
                printf("INF ");
            else
                printf("%d ", dist[i][j]);
        }
        printf("\n");
    }

    return 0;
}