참고 영상: https://youtu.be/hw-SvAR3Zqg
플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘이다. 다익스트라 알고리즘과 마찬가지로 단계별로 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 그렇지만, 매 단계마다 방문하지 않은 노드 중에서 최단 거리의 노드를 찾는 과정은 필요하지 않다.
플로이드 워셜 알고리즘은 매 단계마다 2차원 테이블에 최단 거리 정보를 저장한다는 점에서 다이나믹 프로그래밍 유형이라고 볼 수 있다.
각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 즉, a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
#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억을 넘어서 시간 초과 판정을 받을 수 있다.
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