📌 Intro
이전에 정리했던 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다.
하지만 이번에 살펴볼 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우"에 사용하는 알고리즘이다.
📌 Floyd-Warshall Algorithm
다익스트라 알고리즘은 매 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 과정을 진행하면서 최단 경로 리스트를 수정해나간다. 그리고 이 때 방문한 노드인지 확인하는 과정을 거친다. 하지만 플로이드 워셜 알고리즘은 노드를 방문할 때 방문한 노드인지 아닌지 확인할 필요가 없이 모든 노드에 대해서 동작하는 알고리즘으로 이해하면 된다. 만약 N개의 노드가 존재한다면 알고리즘 상으로 N번의 단계를 수행하며 매 단계마다 O(N²)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 시간 복잡도는 O(N³)이 된다.
정점 1000개까지는 플로이드 워셜 알고리즘을 이용할만 하다. 1000개의 정점이 있는 문제를 해결할 때 소요되는 시간을 줄이는 팁이 있는데 그 방법은 값을 갱신해줄 때 min() 함수 대신 if문을 통해 원하는 조건에서만 대입을 해주는 것이다. 이 방법이 더 빠른 이유는 일반적인 환경에서 연산보다 대입이 느리기 때문이다.
// min 대신 if문을 통해 갱신이 필요할 때만 대입
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
다익스트라 알고리즘은 각 노드까지의 최단 거리를 1차원 배열에 저장했다면 플로이드 워셜 알고리즘은 2차원 배열에 최단 거리를 저장한다. 그래서 매 단계마다 2차원 배열을 처리해야 하므로 O(N²)의 시간 복잡도가 필요한 것이다.
각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해 확인한다면 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하는 것이다. 정확히는 A → 1번 노드 → B 로 가는 비용을 확인한 후 최단 거리를 갱신한다. 만약 A → B로 가는 비용이 3이었을 때 A → 1 → B로 가는 비용이 2라면 더 작은 비용으로 갱신하는 것이다.
그리고 각 단계에서 확인하는 비용의 점화식은 다음과 같다.
A에서 B로가는 최소 비용과 A에서 K를 거쳐 B로 가는 최소 비용을 비교하여 더 작은 값으로 갱신하겠다는 것이다.
플로이드 워셜 알고리즘은 방향 그래프이던, 무방향 그래프이던 상관없다. 또 간선의 가중치가 음수여도 잘 동작하지만 음수인 사이클이 있는 경우 문제가 생긴다.
STEP 0
그림과 표를 예로 들어 더 자세하게 알아보자. 다음은 그래프와 최단 거리가 저장된 2차원 배열의 초기 형태다.
STEP 1
첫 번째로는 1번 노드를 거쳐 가는 경우를 고려한다. 즉 다음과 같은 6가지 경우를 고려하면 된다.
- D23 = min(D23, D21 + D13)
- D24 = min(D24, D21 + D14)
- D32 = min(D32, D31 + D12)
- D34 = min(D34, D31 + D14)
- D42 = min(D42, D41 + D12)
- D43 = min(D43, D41 + D13) D34를 확인하는 것을 예로 들어 설명하면 실제로 그래프에서는 3에서 4로 갈 수 없기 때문에 거리 리스트가 무한대로 초기화 되어 있는 상태다. 하지만 1번을 거치면 3 → 1 → 4로 이동할 수 있고 이 때의 최소 비용은 7이 되는 것이다.
그래프와 거리 리스트를 확인해보면 다음과 같을 것이다. 현재 처리중인 노드와 거리 리스트는 하늘색으로 표시했다.
3 → 2, 3 → 4로 이동하는 최소 비용은 무한대에서 각각 6, 7로 줄어든 것을 확인할 수 있다.
STEP 2
두 번째로는 2번 노드를 거쳐 가는 경우를 고려한다. 즉 다음과 같은 6가지 경우를 고려하면 된다.
- D13 = min(D13, D12 + D23)
- D14 = min(D14, D12 + D24)
- D31 = min(D31, D32 + D21)
- D34 = min(D34, D32 + D24)
- D41 = min(D41, D42 + D21)
- D43 = min(D43, D42 + D23)
그래프와 거리 리스트를 확인해보면 다음과 같을 것이다.
STEP 3
마찬가지로 3번 노드에 대해서 동일한 과정을 진행하면 된다.
STEP 4
마지막 4번 노드에 대해서도 동일한 과정을 진행하면 된다.
FINAL
노드의 개수가 4개이기 때문에 [STEP 4]까지 알고리즘을 진행했다. [STEP 4]가 종료되고 나면 최종적인 거리 리스트는 다음과 같다. 여기에 기록되어 있는 값들은 모든 노드에서 모든 노드로 가는 최단 거리 정보다. 예를 들어 D13값은 4인데, 1번 노드에서 3번 노드로 이동하는 최단 경로의 값이 4라는 의미이다.
📌 구현(C++)
아래 문제를 해결하는 방법을 코드로 구현했다. 설명은 주석으로 달아두었다.
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
#include <iostream>
#define INF 1e15
typedef long long ll;
using namespace std;
int n, m, s, e, d;
ll dist[102][102]; // 2차원 배열(그래프)
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
// 그래프 초기화
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 자기 자신으로의 방향은 0으로 초기화
if (i == j) {
dist[i][j] = 0;
}
// 이외는 최대로 초기화
else {
dist[i][j] = INF;
}
}
}
// A에서 B로 가는 간선이 여러개일 수 있기 때문에 최솟값으로 초기화
for (int i = 0; i < m; i++) {
cin >> s >> e >> d;
dist[s][e] = min(dist[s][e], d);
}
// 플로이드 워셜 알고리즘
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 거리가 수정되지 않았다면 도달할 수 없는 위치
if (dist[i][j] == INF) {
cout << 0 << ' ';
}
else {
cout << dist[i][j] << ' ';
}
}
cout << '\n';
}
return 0;
}📌 경로 복원 방법
플로이드 워셜 알고리즘을 통해 임의의 시작점으로부터 임의의 도착점까지의 최단 거리를 알 수 있다. 그런데 우리는 최단 거리만 알고있을 뿐 최단 경로는 알지 못한다. 그래서 어떤 경로를 통해 최단 거리를 찾아내었는지 경로를 복원해보도록 하자.
A에서 B까지 최단 경로로 가려면 A에서 어느 정점으로 가야하는지를 저장하는 테이블을 nxt테이블이라고 하자. 이 nxt테이블은 최단 거리 테이블을 채우는 과정에서 함께 채워나갈 수 있다. 채워나가는 과정을 위에서 살펴본 그림과 함께 알아보도록 하자.
주어진 그림으로부터 최단 경로 테이블과 nxt 테이블을 채운다.
1번 노드를 통해 이동하는 경로를 고려한다. 이 경우 최단 거리 테이블이 갱신되는 경우는 3 → 2, 3 → 4 경우다. 이 때 nxt 테이블도 갱신해준다. 3 → 2 로 최단 경로로 이동하기 위해서 다음에 방문해야 하는 노드는 1이 돤다. 마찬가지로 3 → 4 로 최단 경로로 이동하기 위해서 다음에 방문해야 하는 노드는 1이 된다.
2번 노드를 통해 이동하는 경로를 고려한다. 이 경우 최단 거리 테이블이 갱신되는 경우는 없다. 때문에 nxt 테이블도 갱신되지 않는다.
3번 노드를 통해 이동하는 경로를 고려한다. 이 경우 최단 거리 테이블이 갱신되는 경우는 4 → 1로 이동하는 경우다. 이 최단 경로를 이용하기 위해 다음에 방문해야 하는 노드는 1이고 nxt 테이블을 갱신해준다.
4번 노드를 통해 이동하는 경로를 고려한다. 이 경우 최단 거리 테이블이 갱신되는 경우는 1 → 3로 이동하는 경우다. 이 최단 경로를 이용하기 위해 다음에 방문해야 하는 노드는 4이고 nxt 테이블을 갱신해준다.
완성된 nxt 테이블은 다음과 같다. 그러면 여기서 어떻게 최단 경로를 알아낼 수 있을까? 1 → 3으로 이동하는 최단 경로를 찾아보자.
가장 먼저 nxt[1][3]을 확인하면 4임을 알 수 있다. 즉, 가장 먼저 4번 노드를 방문해야 하는 것이다. 다음으로는 nxt[4][3]을 확인하면 3임을 알 수 있다. 즉, 다음으로 방문해야 하는 노드는 3이고 우리가 원하는 도착지점과 같다. 마지막으로 nxt[3][3]을 확인하면 0인 것을 알 수 있다. nxt[3][3]까지 확인하는 이유는 코드상에서 예외처리 없이 마지막까지 자연스럽게 확인하기 위함이다.
📌 구현(C++)
아래 문제를 해결하는 방법을 코드로 구현했다.
11780번: 플로이드 2
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
#include <iostream>
#include <queue>
#define INF 1e9
using namespace std;
int n, m, s, d, e;
int dist[102][102];
int nxt[102][102];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 자기 자신으로의 이동 값은 0으로 세팅
if (i == j) {
dist[i][j] = 0;
}
// 나머지는 최대로 초기화
else {
dist[i][j] = INF;
}
}
}
for (int i = 0; i < m; i++) {
cin >> s >> e >> d;
dist[s][e] = min(dist[s][e], d);
nxt[s][e] = e;
}
// 플로이드 워셜 알고리즘
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
nxt[i][j] = nxt[i][k];
}
}
}
}
// 최단 거리 출력
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == INF) {
cout << 0 << ' ';
}
else {
cout << dist[i][j] << ' ';
}
}
cout << '\n';
}
// i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == 0 || dist[i][j] == INF) {
cout << 0 << '\n';
continue;
}
queue<int> route;
route.push(i);
int location = nxt[i][j];
while (location != j) {
route.push(location);
location = nxt[location][j];
}
route.push(j);
cout << route.size() << ' ';
while (!route.empty()) {
cout << route.front() << ' ';
route.pop();
}
cout << '\n';
}
}
return 0;
}s에서 e로 이동하는 경우 1번 정점을 거쳐서 이동하는 경우가 더 최단 경로일 경우 dist[s][e]값을 dist[s][1] + dist[1][e]로 갱신한다. 이 때 nxt[s][e] 또한 변경이 필요하고 기존의 s에서 e로가는 경로보다 s에서 1을 거치고 1에서 e로 가는 경로가 더 효율적인 상황이니 nxt[s][e]값을 nxt[s][1]로 갱신해주면 된다. s에서 1을 갔다가 e까지는 어떻게 가는지 모르겠지만 일단 1로 가야함이 자명하고 s에서 e까지 최단 경로로 가기 위해서는 일단 nxt[s][1]로 가야한다.
📌 정리
플로이드 워셜 알고리즘은 무방향 혹은 방향 그래프에서 모든 정점 쌍 사이의 최단 거리와 그 경로를 O(V³)안에 알아낼 수 있다. 주어진 그래프에서 정점의 수가 1000개 이하인 경우 플로이드 워셜 알고리즘을 사용할 수 있다.
참고
[1] 이것이 취업을 위한 코딩테스트다 with 파이썬
[2] https://www.youtube.com/watch?v=dDDy2bEZRA8
