참고 영상: https://youtu.be/hw-SvAR3Zqg

알고리즘 이해

플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘이다. 다익스트라 알고리즘과 마찬가지로 단계별로 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 그렇지만, 매 단계마다 방문하지 않은 노드 중에서 최단 거리의 노드를 찾는 과정은 필요하지 않다.

플로이드 워셜 알고리즘은 매 단계마다 2차원 테이블에 최단 거리 정보를 저장한다는 점에서 다이나믹 프로그래밍 유형이라고 볼 수 있다.

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 즉, a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.

$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

---

코드로 구현

#include <iostream>
#define INF 1e9
#define MAX 101
using namespace std;

int n, m; // 노드, 간선 개수 
int dist[MAX][MAX]; // 두 노드 간의 비용을 저장하는 2차원 배열 

void input() {
	cin >> n >> m;

    // 최단 거리 테이블 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }

    // A에서 B로 가는 비용은 C라고 설정
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;

        // 동일한 간선이 또 입력될 경우, 비용이 더 작은 값으로 초기화!!!
        if (dist[a][b] > c) dist[a][b] = c;
    }
}

void floyd() {
	// 점화식에 따라 플로이드 워셜 알고리즘 수행
    for (int k = 1; k <= n; k++) {
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                // 자기 자신에서 자기 자신으로 가는 경로는 제외
                if (a == b) continue;
				
                // 경유하는 k번 노드는 출발, 도착 노드에서 제외
                if (a == k || b == k) continue;

                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);
            }
        }
    }
}

void printResult() {
 	for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            if (dist[a][b] == INF) cout << 0 << ' '; 
            else cout << dist[a][b] << ' ';
        }
        cout << '\n';
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

	input(); 

	floyd();

	printResult();

	return 0; 
}

---

시간복잡도 분석

	for (int k = 1; k <= n; k++) {
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                // 자기 자신에서 자기 자신으로 가는 경로는 제외
                if (a == b) continue;
                
                // 경유하는 k번 노드는 출발, 도착 노드에서 제외
                if (k == a || k == b) continue;

                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);
            }
        }
    }

노드의 개수가 n개일 때, 각 단계마다 O(n^2) 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려하기 때문에 시간복잡도는 O(n^3)이다. 따라서 노드 개수가 500개 이상이면 1억을 넘어서 시간 초과 판정을 받을 수 있다.

---

백준 11404번

https://www.acmicpc.net/problem/11404

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

처음 풀 때 이 조건을 놓쳐서 틀렸다.

5
14
1 2 2
1 3 3
1 4 1 ←
1 5 10
2 4 2
3 4 1 ←
3 5 1 ←
4 5 3
3 5 10 ←
3 1 8
1 4 2 ←
5 1 7
3 4 2 ←
5 2 4

문제에 주어진 위의 입력 예시처럼 두 노드를 연결하는 간선이 여러 개일 경우, 더 작은 비용으로 초기화 해야 한다. 즉, 이미 테이블에 저장한 비용보다 새로 입력된 간선의 비용이 더 작을 때만 값을 바꿀 수 있도록 한다.

// A에서 B로 가는 비용은 C라고 설정
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;

        // 동일한 간선이 또 입력될 경우, 비용이 더 작은 값으로 초기화!!!
        if (graph[a][b] > c) 
            graph[a][b] = c;
    }

cf) 플로이드 워셜 알고리즘 관련 추가 문제
https://www.acmicpc.net/problemset?search=%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C