그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다.
하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)
하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)
하나의 목적지로가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)
마지막으로 모든 최단 경로를 구하는 문제(All pairs shortest path problem)이다.
다익스트라 알고리즘은 여기서 두번째 방법으로, 하나의 정점에서 다른 모든 정점들의 최단 경로를 구한다.
간선들은 모두 양의 간선들을 가져야 한다.
다익스트라 알고리즘의 기본 로직은, 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다.
정점을 잇기 전까지는 시작점을 재외한 정점들은 모두 무한대 값을 가진다.
정점 A에서 정점 B로 이어지면, 정점 B가 가지는 최단 거리는 시작점부터 정점 A까지의 최단 거리 + 점A와 점B 간선의 가중치와, 기존에 가지고 있던 정점 B의 최단 거리중 작은 값이 B의 최단 거리가 된다.
1. 다익스트라 알고리즘 기본 로직
다음과 같은 그래프가 있다. 여기서 시작점은 5번 정점이라고 해보자.
여기서 5번 노드를 제외한 나머지 정점들이 가지는 최단 경로는 아직 연결되지 않았으므로 무한대이다.
5 |
4 |
3 |
2 |
1 |
0 |
INF |
INF |
INF |
INF |
여기서 경로가 가장 짧은 정점을 고른다. 여기선 5번 노드이다. 5번 노드와 연결되어있는 노드는 2,4번 노드이다.
먼저 2번노드부터 보자. 2번 노드의 최단 거리를 가지고있는 현재 최단거리(INF)와, 5번 노드의 최단거리(0) + 2번-5번의 가중치(4) 값 중 가장 작은 값으로 갱신한다. 즉, dist[2] = min(dist[2], dist[5] + adj[5][2])을 구한다 이는 min(INF,4)이므로 4가 된다.
4번 노드 또한 4번 노드의 최단 거리를 가지고있는 현재 최단거리(INF)와, 5번 노드의 최단거리(0) + 4번-5번의 가중치(2) 값 중 가장 작은 값으로 갱신한다.
즉, dist[4] = min(dist[4], dist[5] + adj[5][4])을 구한다. min(INF,2)이므로 2가 된다.
5 | 4 | 3 | 2 | 1 |
0 | INF | INF | INF | INF |
| 2 | | 4 | |
이제 나머지 정점 중에서 경로가 가장 짧은 정점을 고른다. 가장 짧은 거리를 가지고 있는 노드는 2의 길이를 가지고 있는 4번 노드이다.
이제 4번 노드의 인접노드는 2,3번 노드이다.
2번 정점의 최단 거리를 가지고있는 현재 최단거리(4)와, 4번 정점의 최단거리(2) + 2번-4번의 가중치(1) 값 중 가장 작은 값으로 갱신한다.
즉, dist[2] = min(dist[2], dist[4] + adj[4][2])을 구한다
2번 정점의 기존 최단 거리 dist[2]는 4고, dist[4] + adj[4][2]는 3이므로 3으로 갱신된다.
또한 3번 정점은 의 최단 경로 dist[3]은 INF이므로, dist[4] + adj[4][3] = 3으로 갱신한다.
5 | 4 | 3 | 2 | 1 |
0 | INF | INF | INF | INF |
| 2 | | 4 | |
| | 3 | 3 | |
위와 같은 방법을 반복한다. 3,2번 정점의 최단 경로가 똑같으므로 숫자적으로 앞에 있는 2번 경로를 꺼내고, 인접 정점을 비교한다.
인접 정점은 1로 간선 가중치는 3이다. 따라서 dist[1] = min(dist[1], dist[2] + adj[2][1])을 구한다. dist[1]은 INF이므로, dist[2] + adj[2][1]인 6으로 갱신된다.
5 | 4 | 3 | 2 | 1 |
0 | INF | INF | INF | INF |
| 2 | | 4 | |
| | 3 | 3 | |
| | | | 6 |
최단 경로가 3인 정점 3을 꺼내고 인접 정점을 비교한다. 인접 정점은 4다. dist[4] = min(dist[4], dist[3] + adj[3][4])를 계산한다.
dist[4] 는 2이고,dist[3] + adj[3][4]는 5이다. dist[4]가 더 작으므로 그대로 유지된다.
5 | 4 | 3 | 2 | 1 |
0 | INF | INF | INF | INF |
| 2 | | 4 | |
| | 3 | 3 | |
| |
| | 6 |
마지막으로 남은 정점은 1이다. 1을 꺼내고 인접 정점을 비교한다. 인접 정점은 3과 4다.
dist[4] = min(dist[4], dist[1] + adj[1][4])를 계산한다.
dist[4] 는 2이고,dist[1] + adj[1][4]는 9이다. dist[4]가 더 작으므로 그대로 유지된다.
dist[3] = min(dist[], dist[6] + adj[6][3])를 계산한다.
dist[3] 는 3이고,dist[1] + adj[1][3]는 9이다. dist[4]가 더 작으므로 그대로 유지된다.
5 | 4 | 3 | 2 | 1 |
0 | INF | INF | INF | INF |
| 2 | | 4 | |
| | 3 | 3 | |
| | | | 6 |
모든 정점을 방문했다. 완성한 테이블이 5번 정점부터 나머지 정점까지의 최단 경로이다.
2. 우선순위 큐(힙구조)를 이용한 다익스트라 알고리즘
위 방법은 배열을 매번 탐색해서 가장 짧은 거리를 찾는 방법이다.
하지만 힙 구조를 이용하면 더욱 빠른 시간 내에 구현이 가능하다.
최소 힙을 사용하면 가장 작은 경로를 가진 정점이 나오도록 구현하면 되기 때문이다.
그래프를 다시 한번 보자.
모든 정점들을 힙(우선순위 큐)에 넣는다.
dist배열
5 | 4 | 3 | 2 | 1 |
0 | INF | INF | INF | INF |
위 표에서 i는 정점 인덱스, d는 최단 거리이고 p는 이전 정점이다. d를 기준으로 최소 힙으로 구성한다.
힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 5이고 최소 거리가 0인 값이다.
기존에 있던 dist[5]와 d를 비교한다. dist[5]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.
둘 다 0으로 같으므로, 5 주변의 인접 정점을 계산하고 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.(dist[2] = min(dist[2], dist[5] + adj[5][2], dist[4] = min(dist[4], dist[5] + adj[5][4])
dist배열
힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 4이고 최소 거리가 2인 값이다.
기존에 있던 dist[4]와 d를 비교한다. dist[4]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.
dist[4]는 2이고, d는 2로 같으므로,
4 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.(dist[2] = min(dist[2], d + adj[4][2], dist[3] = min(dist[3], d + adj[4][3]))
dist배열
힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 2이고 최소 거리가 3인 값이다.
기존에 있던 dist[2]와 d를 비교한다. dist[2]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.
dist[2]는 3이고, d는 3으로 같으므로,
2 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.(dist[1] = min(dist[1], dist[2] + adj[2][1]))
dist배열
힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 3이고 최소 거리가 3인 값이다.
기존에 있던 dist[3]와 d를 비교한다. dist[3]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.
dist[3]는 3이고, d는 3으로 같으므로,
2 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는정점들을 큐에 넣는다.(dist[4] = min(dist[4], dist[4] + adj[4][2]))
여기서 dist[4]는 2로 계산값보다 더 작으므로 큐에 넣지 않는다.
dist배열
힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 2이고 최소 거리가 4인 값이다.
dist[2]=3보다 d=4가 더 크므로 계산하지 않는다.
dist배열
힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 1이고 최소 거리가 7인 값이다.
기존에 있던 dist[1]와 d를 비교한다.dist[1]는 7이고, d는 7로 같으므로,
1 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는정점들을 큐에 넣는다.(dist[4] = min(dist[4], dist[1] + adj[1][4]),dist[3] = min(dist[3], dist[1] + adj[1][3]))
둘 다 기존의 dist[i]보다 크므로 큐에 넣지 않는다.
dist배열
큐에 남아있는 정점들은 전부 d가 INF로 dist[i]보다 크므로 계산되지 않는다.
이를 구현한 코드는 밑과 같다. 위에선 작성되어 있지 않지만 갱신 시마다 위의 정보들을 map에 넣어주면 경로를 쉽게 구할 수 있다.
이 또한 코드에서 구현해보았다.
3. C++ 우선순위 큐 다익스트라 알고리즘 코드
#include <cstdio>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <utility>
#define MAX_VALUE -987654321
using namespace std;
int n, m, s;
class Vertex {
public:
int index;
int dist;
int post = 0;
Vertex(int index, int dist, int post) :index(index), dist(dist), post(post) {
}
Vertex(int index) :index(index) {
dist = MAX_VALUE;
}
void setDist(int d) {
dist = d;
}
bool operator >(const Vertex& v) const {
return dist > v.dist;
}
bool operator <(const Vertex& v) const {
return dist < v.dist;
}
};
class Graph {
public:
int n = 0;
vector<Vertex> vt;
vector<vector<pair<int, int> > > adj;
priority_queue<Vertex > pq;
map<int, pair<int, int> > m;
void addVertex(int index, int dist) {
vt.push_back(Vertex(index, dist, index));
n = vt.size();
adj.resize(n + 1);
}
void addVertex(int index) {
vt.push_back(Vertex(index));
n = vt.size();
adj.resize(n);
}
void addAdj(int u, int v, int w) {
adj[u - 1].push_back(make_pair(v, w));
}
void setStart(int index) {
vt[index - 1].setDist(0);
vt[index - 1].post = index;
}
void dijkstra(int s) {
vector<int> dist(n, -1 * MAX_VALUE);
dist[s - 1] = 0;
setStart(s);
for (int i = 0; i<n; i++) {
pq.push(vt[i]);
}
m.insert(make_pair(s, make_pair(0, -1)));
while (!pq.empty()) {
int index = pq.top().index - 1;
int cost = -1 * pq.top().dist; pq.pop();
if (dist[index] < cost) continue;
for (int i = 0; i<adj[index].size(); i++) {
int n = adj[index][i].first;
int v = adj[index][i].second;
if (dist[n - 1] > dist[index] + v) {
dist[n - 1] = dist[index] + v;
Vertex newVt = Vertex(n, -dist[n - 1], index + 1);
pq.push(newVt);
m[n] = make_pair(dist[n - 1], index + 1);
}
}
}
printf("인덱스 별 최단 경로 길이\n");
for (int i = 0; i<n; i++) {
printf(dist[i] != -1 * MAX_VALUE ? "%d " : "INF ", dist[i]);
}
printf("\n\n인덱스 - 최단 경로 - 이전 정점\n");
for (int i = 1; i <= m.size(); i++) {
printf("%d - %d - %d\n", i, m[i].first, m[i].second);
}
printf("\n");
for (int i = 1; i <= n; i++) {
printf("%d까지 경로 : ", i);
if (dist[i - 1] != -MAX_VALUE) {
stack<int> st;
int next = m[i].second;
while (next != -1) {
st.push(next);
next = m[next].second;
}
while (!st.empty()) {
printf("%d - ", st.top());
st.pop();
}
printf("%d\n", i);
}
}
}
};
int main() {
scanf("%d %d %d", &n, &m, &s);
Graph gp;
for (int i = 0; i<n; i++) {
gp.addVertex(i + 1);
}
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
gp.addAdj(u, v, w);
}
gp.dijkstra(s);
}
<실행 화면>
