[Algorithm] 플로이드 와샬(Floyd-Warshall) 알고리즘
그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있습니다. 플로이드 와샬 알고리즘에 대해서 알아보기 전에 이에 대해서 간단히 살펴보도록 하겠습니다.
-
하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제
single source and single destination shortest path problem
-
하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
single source shortest path problem
-
하나의 목적지로가는 모든 최단 경로를 구하는 문제
single destination shortest path problem
-
모든 최단 경로를 구하는 문제
all pairs shortest path problem
Floyd-Warshall 알고리즘이란?
Floyd-Warshall 알고리즘이란, 위 경우에서 마지막에 해당하는 모든 최단 경로를 구하는 방법 입니다. 다익스트라와 벨만포드가 두 번째에 해당하는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 방법 과는 다릅니다.
알고리즘
Floyd-Warshall 알고리즘을 통해 모든 최단 경로를 구할 수 있습니다. 그러기 위해서 이 정보를 저장할 인접행렬 W 를 만들어주도록 합시다. 인접행렬 W의 크기는 노드의 개수 V에 대해 V X V 의 크기를 가지며, W[i][j] 는 i 번째 노드부터 j 번째 노드까지 가중치 가 됩니다.
다음 그래프에 대해서는 인접행렬 W가 아래와 같이 생기게 됩니다.
0 3 8 INF -4
INF 0 INF 1 7
INF 4 0 INF INF
2 INF -5 0 INF
INF INF INF 6 0
이 때 INF 는 무한대로 이동하는 경로가 없다는 의미입니다.
이를 통해 최단경로 행렬 D 를 만들 수 있습니다.
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2-1 -5 0 -2
해당 행렬 D[i][j] 는 i 번째 노드에서 j 번째 노드까지의 최단 경로 를 의미합니다. 예를 들어 1 에서 3 까지의 최단경로를 보면 -3 이고 이는 1->5->4->3 으로 이동할 경우, -4+6+-5 = -3 이 됨을 알 수 있습니다.
그렇다면 W 인접행렬을 통해 D 최단경로 행렬을 어떻게 만들 수 있을까요?
정점 집합 {1,...,n} 에 대해서 i,j 가 V 에 포함될 때 i와 j사이에 정점 집합 V 에 속하는 모든 정점을 넣어보고 경로의 값이 가장 작아지는 경로를 찾는다.
다음과 같이 언어로 보는 것보단 수식으로 보는게 더 이해하기 쉽습니다.
이 때 dij^(k) 를 k 라는 정점을 이번에 추가하였을 때 i 정점부터 j 정점까지의 최단경로 라고 정의합니다.
즉 k 라는 정점을 새로 추가하였을 때 i 정점부터 j 정점까지의 최단경로는 기존의 i 정점 부터 j 정점까지 이동했던 경로 와 i 정점부터 k 정점까지의 최단 경로 + k 정점부터 j 정점까징의 최단 경로 중 최소값이 됩니다.
다음과 같은 방법으로 플로이드 와샬 알고리즘은 중간 정점을 모두 실험해보게 됩니다.
전체적인 수도코드는 다음과 같습니다.
D 행렬의 변화를 전부 다 확인하기는 힘들 것 같고 W 에 해당하는 D(0) 가 D(1) 으로 바뀌는 과정만 같이 보도록 하겠습니다.
// D(0)
0 3 8 INF -4
INF 0 INF 1 7
INF 4 0 INF INF
2 INF -5 0 INF
INF INF INF 6 0
// D(1)
0 3 8 INF -4
INF 0 INF 1 7
INF 4 0 INF INF
2 5 -5 0 -2
INF INF INF 6 0
바뀐 부분을 살펴보면 D[3][1] , D[3][4] 입니다. 4번 정점는 1번 정점를 통해서 2번 정점와 5번 정점으로 갈 수 있게 되었기 때문에 값이 갱신되었고 각 값은 5,-2 입니다.
Floyd-Warshall 경로구하기
최단 경로 행렬 D 를 통해 i 번째 정점에서 j 번째 정점까지 최단경로를 구할 수 있었습니다. 정확히는 최단경로로 갈 때의 가중치를 구하는 것이기 때문에 어떤 정점을 거쳐 가는지는 알 수 없습니다.
따라서 이를 위해 직전 정점 행렬 pi 를 정의해보도록 합시다.
pi[i][j] 는 i 정점에서 j 정점까지의 경로에서 j 정점 직전에 나오는 정점을 의미합니다.
예를 들어 1에서 3까지의 경로를 구해보도록 하겠습니다. 예시를 위해 완성된 pi 행렬을 살펴보면 아래와 같습니다.
- 3 4 5 1
4 - 4 2 1
4 3 - 2 1
4 3 4 - 1
4 3 4 5 -
우선 1 정점에서 출발해서 3 정점에서 끝나므로 경로의 시작은 1, 끝은 3 입니다. 3 직전에 오는 정점은 pi[0][2] 인 4가 됩니다. ( index를 0부터 시작하기 때문에 하나씩 차이가 납니다. )
현재 경로는 1 -> 4 -> 3 이 됩니다.
이제 다시 1 정점에서 4 정점 까지의 경로를 구하기 위해 pi[0][3] 의 값 5를 참조합니다.
현재 경로는 1-> 5 -> 4 -> 3 이 됩니다.
1 정점에서 5정점까지의 경로를 구하기 위해 pi[0][4] 의 값 1 을 참조합니다.
경로가 1-> 1 로 같은 정점이 연속적으로 나온다는 의미는 경로가 완성되었음을 의미합니다.
따라서 완성된 경로는 1-> 5 -> 4 -> 3 가 됩니다.
직전 정점 행렬 pi 가 주어졌을 때 경로를 구하는 방법을 알았으니 pi 행렬을 만들어보도록 합시다.
pi 행렬도 D 행렬과 마찬가지로 가장 바깥 for 문이 돌면서 갱신이 됩니다.
먼저 pi(0) 부터 본다면 다음과 같습니다.
- 1 1 - 1
- - - 2 2
- 3 - - -
4 - 4 - -
- - - 5 -
W[i][j] 의 값이 존재한다면, 즉 i 정점에서 j 정점까지의 경로가 있다면 출발정점 i 를 넣어줍니다.
다음으로 pi(1) 은 다음과 같습니다.
- 1 1 - 1
- - - 2 2
- 3 - - -
4 1 4 - 1
- - - 5 -
1번 정점을 통해 i 에서 j 까지 경로가 생겼다면 pi[i][j] 에 1 을 넣어주도록 합시다.
마찬가지로 pi(k) 에 대해서 k 번 정점을 통해서 i 에서 j 까지 경로가 생겼고 그 경로가 최단경로라면 pi[i][j] 에 k 를 넣어주도록 합니다.
이 과정을 반복한다면 다음과 같습니다.
// pi(2)
- 1 1 2 1
- - - 2 2
- 3 - 2 2
4 1 4 - 1
- - - 5 -
// pi(3)
- 1 1 2 1
- - - 2 2
- 3 - 2 2
4 3 4 - 1
- - - 5 -
// pi(4)
- 1 4 2 1
4 - 4 2 1
- 3 - 2 1
4 3 4 - 1
- - - 5 -
구현
위에서 정의했던 행렬 D 를 graph 행렬로 정의하고, 행렬 pi 를 before 행렬로 정의하였습니다.
#include <iostream>
using namespace std;
#define INF 987654321
#define NIL -1
#define MAX 101
int graph[MAX][MAX];
int before[MAX][MAX];
void floyd(int n){
for (int mid=1;mid<=n;mid++){
for (int start=1;start<=n;start++){
for (int end=1;end<=n;end++){
if (graph[start][end] > graph[start][mid] + graph[mid][end]){
// 더 가까운 경로가 있을 경우 최신화
graph[start][end] = graph[start][mid] + graph[mid][end];
// 직전정점 행렬 최신화
before[start][end] = before[mid][end];
}
}
}
}
}
int main(){
// n: 정점의 수, m: 간선의 수
int n,m;
cin >> n >> m;
// graph 와 before 초기화
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
graph[i][j] = MAX;
if (i==j) graph[i][j] = 0;
before[i][j] = NIL;
}
}
for (int i=0;i<m;i++){
int node1, node2, w;
cin >> node1 >> node2 >> w;
graph[node1][node2] = w;
before[node1][node2] = node1;
}
cout << "초기값\n";
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cout << graph[i][j] << "\t";
}
cout << "\n";
}
cout << "\n";
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cout << before[i][j] << "\t";
}
cout << "\n";
}
floyd(n);
cout << "최종값\n";
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cout << graph[i][j] << "\t";
}
cout << "\n";
}
cout << "\n";
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cout << before[i][j] << "\t";
}
cout << "\n";
}
}
초기값
0 3 8 101 -4
101 0 101 1 7
101 4 0 101 101
2 101 -5 0 101
101 101 101 6 0
-1 1 1 -1 1
-1 -1 -1 2 2
-1 3 -1 -1 -1
4 -1 4 -1 -1
-1 -1 -1 5 -1
최종값
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0
-1 3 4 5 1
4 -1 4 2 1
4 3 -1 2 1
4 3 4 -1 1
4 3 4 5 -1
경로 찾기
1부터 2까지의 경로 : 1 5 4 3 2
1부터 3까지의 경로 : 1 5 4 3
1부터 4까지의 경로 : 1 5 4
1부터 5까지의 경로 : 1 5
2부터 1까지의 경로 : 2 4 1
2부터 3까지의 경로 : 2 4 3
2부터 4까지의 경로 : 2 4
2부터 5까지의 경로 : 2 4 1 5
3부터 1까지의 경로 : 3 2 4 1
3부터 2까지의 경로 : 3 2
3부터 4까지의 경로 : 3 2 4
3부터 5까지의 경로 : 3 2 4 1 5
4부터 1까지의 경로 : 4 1
4부터 2까지의 경로 : 4 3 2
4부터 3까지의 경로 : 4 3
4부터 5까지의 경로 : 4 1 5
5부터 1까지의 경로 : 5 4 1
5부터 2까지의 경로 : 5 4 3 2
5부터 3까지의 경로 : 5 4 3
5부터 4까지의 경로 : 5 4