37. Floyd-Warshall 알고리즘

플로이드-워셜 알고리즘이란?

지금까지의 최단거리 알고리즘은 하나의 시작 노드에서 모든 노드까지 가는 최단거리를 구한 것이다.

플로이드-워셜 알고리즘은 모든 노드 쌍 사이의 최단거리를 찾는 알고리즘이다.

벨만-포드 알고리즘과 마찬가지로 음의 가중치를 가지는 그래프에도 적용이 가능하다.

---

플로이드-워셜 알고리즘 기본 아이디어

1. 노드의 개수를 N이라고 할 때, N X N 크기의 2차원 배열 dist를 생성하여 최단거리를 저장한다.

dist[i][j]는 노드 i에서 노드 j로 가는 최단거리를 의미한다.

2. 초기 단계에서 dist 배열을 입력 그래프의 가중치로 초기화한다. 만약 직접 가는 길이 없다면 INF로 설정한다.

3. 세 개의 반목문을 사용하여 모든 노드 쌍 사이의 최단거리를 찾는다.

4. dist[i][j]와 dist[i][k] + dist[k][j]를 비교하여 작은 값을 dist[i][j]에 저장한다.

---

플로이드-워셜 알고리즘 구현

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_N 100
#define INF INT_MAX

int dist[MAX_N][MAX_N];

void floyd_warshall(int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 초기화
    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] = INF;
            }
        }
    }
    
    // 그래프 입력
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        scanf("%d %d %d", &u, &v, &weight);
        dist[u][v] = weight;
    }
    
    floyd_warshall(n);
    
    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                printf("INF ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
    
    return 0;
}

노드의 개수가 N개라면 시간복잡도는 O(N^3)이다.