최단 경로 advence
본격적으로 최단 경로 알고리즘에 대해 알아보자.
플로이드 와샬 알고리즘
플로이드 와샬 알고리즘은 3중 for문으로 구현하여 최단 경로를 알아내는 알고리즘이다.
본격적으로 구현하기 전에 몇가지 세팅이 필요한데...
우선 연결 관계를 표현할 배열이 하나 필요하다.
그리고, 자기 자신으로 가는 것은 최단 경로가 0이므로 그대로 둔다.
입력은 두 정점과 가중치가 주어진다.
두 정점이 연결되어 있다는 것을 배열의 [정점A][정점B] = 가중치의 형식으로 나타낸다.
정점들의 연결 관게와 가중치가 모두 처리 되었다면!
자기 자신으로 가는 경우에는 0으로 처리하고, 배열에 저장된 값이 없으면 절대 나올 수 없는 수로 처리해 준다.
이제 본격적으로 플로이드 와샬 알고리즘을 사용해 최단 경로를 구할 건데...
원리는 다음과 같다.
i -> j 로 가는 경로보다 i -> j로 가는 도중 k 를 경유해서 가는 비용이 더 작으면 갱신해 준다.
여기서 아까 절대 나올 수 없는 수로 처리해준 이유가 나오는데,
0으로 설정되어 있으면 최소값을 찾을 수 없으므로 이것을 절대 나올 수 없는 수로 처리해서 최소를 갱신할 수 있게 만들어준다.
플로이드 와샬 알고리즘을 구현한 코드는 다음과 같다.
|
1
2
3
4
5
6
7
|
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
}
}
}
|
cs |
다익스트라 알고리즘
다익스트라 알고리즘은 기본적으로 BFS를 이용해서 구현을 한다. 즉, queue를 이용해 구현하는 것이 보통이다.
시작 정점을 queue에 0과 함께 넣어준다. ( 자기 자신으로 가는 최소 비용은 0이기 때문이다. )
그리고, 최단 경로를 저장하는 배열에다가 시작 정점의 위치에 0으로 지정해 준다.
이제 queue를 이용해 BFS를 진행할 건데,
만약 최소보다 도착하려는 정점의 비용이 더 큰 경우에는 넘어간다.
그러면 그 다음에 cost는 그래프에서 현재까지 연산된 비용 + 다음 정점으로 가는 비용이 된다.
만약 cost가 최단 경로를 저장하는 배열에서 다음 정점 위치에 저장된 비용보다 작다면, 최소 비용을 갱신해 준다.
구현된 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
/*
ID : Literhyeon
LANG : C++
*/
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int shortest[20010], INF = 987654321;
vector<pair<int, int>> G[20010];
queue<pair<int, int>> pq;
void dijkstra(int st) {
pq.push({0, st});
shortest[st] = 0;
while(!pq.empty()) {
int dist = -pq.top().first;
int now = pq.top().second;
pq.pop();
if(dist > shortest[now]) continue;
for(int i=0; i<G[now].size(); i++) {
int cost = dist + G[now][i].second;
int next = G[now][i].first;
if(cost < shortest[next]) {
shortest[next] = cost;
pq.push({-cost, next});
}
}
}
}
int main()
{
int v, e, k; cin >> v >> e >> k;
while(e--) {
int x, y, w; cin >> x >> y >> w;
G[x].push_back({y, w});
}
for(int i=1; i<=v; i++) shortest[i] = INF;
dijkstra(k);
for(int i=1; i<=v; i++) {
if(shortest[i] == INF) {
cout << "INF\n";
} else {
cout << shortest[i] << "\n";
}
}
return 0;
}
|
cs |
여기서 시간복잡도를 더 줄이려면 힙을 사용하는 방법이 있다.
힙을 사용하여 다익스트라를 구현하면 O(nm log n) 이라는 시간 복잡도가 완성이 된다.