하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 Algorithm이다.
벨만 포드 방식과 차이점을 반드시 이해해야 한다.
- Greedy algorithm을 활용한 대표적인 최단경로 탐색 Algorithm이다.
- 흔히 인공위성, GPS 등에 가장 많이 사용된다.
- 간선의 가중치는 음수가 될 수 없다.
- 따라서 현실세계에 가장 적합한 Shortest Path Algorithm이다.
- 벨만 포드 알고리즘과의 가장 큰 차이이다.
기본 원리
벨만 포드 알고리즘은 “한 번이라도 방문한 모든 정점” 을 탐색하며 최단 경로를 찾는다.
하지만 다익스트라 알고리즘은 “방문하지 않은 정점 중 가중치가 최소인 정점” 을 탐색한다.
따라서, 기본적으로 시간 복잡도가 벨만 포드 알고리즘보다 낮다.
아래의 예시들을 보며 기본 원리를 이해해보자.
Example : Basic Dijkstra, O(N^2)
-
아래와 같은 Graph가 있다고 생각해보자.
- STEP 1
- 출발 정점을 1이라고 했을 때, 제일 처음엔 출발 노드로부터 이어진 다른 Node까지의 모든 비용을 저장한다.
- 그럼 위와 같은 표가 만들어진다.
- 출발 정점을 1이라고 했을 때, 제일 처음엔 출발 노드로부터 이어진 다른 Node까지의 모든 비용을 저장한다.
- STEP 2
- 이제 최단 경로를 찾을 수 있도록 계속 갱신을 해야한다.
- 방문하지 않은 Node중에서 가장 비용이 적은 4번 Node부터 들려서 갱신을 해보자.
- 4번 Node를 거쳐서 갈 수 있게 된 Node나, 더 나은 경로가 있으면 아래와 같이 갱신한다.
- 이제 최단 경로를 찾을 수 있도록 계속 갱신을 해야한다.
- STEP 3
- 남은 미 방문 Node들도 모두 돌며 똑같이 반복한다.
- 최종적으로 갱신이 완료된 시점의 최단 경로 표는 아래와 같다.
- 최종적으로 갱신이 완료된 시점의 최단 경로 표는 아래와 같다.
- 남은 미 방문 Node들도 모두 돌며 똑같이 반복한다.
- 구현 Code는 아래와 같다.
#include <iostream>
#include <vector>
using namespace std;
#define INF 1000000000
int nodes = 0, edges = 0, start = 0;
vector<pair<int, int>> graph[100001]; // 연결된 node와 weight
bool visit[100001];
int dist[100001];
// 자신을 제외한 방문하지 않은 Node 중 weight이 가장 작은 Node 번호.
int which_smallest() {
int min = INF;
int idx = 0;
for (int i = 0; i <= nodes; i++) {
if (dist[i] < min && !visit[i]) {
min = dist[i];
idx = i;
}
}
return idx;
}
void dijkstra(int start) {
dist[start] = 0; // 자신의 거리는 0으로 초기화
visit[start] = true; // 자신은 방문한 것으로 표시
for (int i = 0; i < graph[start].size(); i++) {
dist[graph[start][i].first] = graph[start][i].second;
} // 거리 배열에, 시작 node와 연결된 모든 Node까지의 가중치 적립.
for (int i = 0; i < nodes - 1; i++) {
int curr_node = which_smallest();
visit[curr_node] = true;
// 방문하지 않은 node 중 가중치가 가장 적은 node 선택
for (int j = 0; j < graph[curr_node].size(); j++) {
int cost = dist[curr_node] + graph[curr_node][j].second;
// 현재 지정된 node와 연결된 다른 node와의 거리를 더해본다.
// ex) curr_node가 2면, 1 - 2 - 4 & 1 - 2 - 3 으로 두 번 돈다.
if (cost < dist[graph[curr_node][j].first]) {
dist[graph[curr_node][j].first] = cost;
// 만약 해당 경로에 대해서 원래 dist 배열의 가중치보다 cost가 작다면,
// 교체 한다.
// ex) curr_node가 1 - 4 보다, 1 - 2 - 4가 더 짧은 거리이면 교체.
}
}
}
}
int main() {
cin >> nodes >> edges >> start;
for (int i = 0; i < edges; i++) {
int u = 0, v = 0, weight = 0;
cin >> u >> v >> weight;
graph[u].push_back(make_pair(v, weight));
} // 입력
fill_n(dist, 100001, INF); // 초기 Dist는 모두 INF로 초기화
dijkstra(start);
for (int i = 1; i <= nodes; i++) {
if (dist[i] == INF) cout << "INF" << '\n';
else cout << dist[i] << '\n';
}
return 0;
}Example : Dijkstra with Min Heap, O(Edge * log(Vertex))
위의 예제는 O(N^2)으로 풀어내는 다익스트라였다.
이번엔 좀 더 효율적인 알고리즘을 위해 STL을 사용해 보자.
다음과 같은 점을 이용한다.
- 어차피 우리는 가중치가 가장 작은 node를 선택해 나갈 것이다.
- 이는 Priority Queue에 넣었다 빼면, 자동으로 뽑혀 나올 것!
#include <vector>
#include <queue>
using namespace std;
#define INF 100000000
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> node_q;
vector<pair<int, int>> maps[51];
int dist[51];
void make_map(vector<vector<int>> road) {
for (auto i : road) {
maps[i[0]].push_back({ i[1], i[2] });
maps[i[1]].push_back({ i[0], i[2] });
}
} // 지도, 인접 리스트로 구현
void init_dist(int n) {
for (int i = 1; i < n + 1; i++)
dist[i] = INF;
} // 거리 배열은 모두 INF(무한)로 초기화
void dijkstra(int start) {
dist[start] = 0;
node_q.push({ 0, start });
// first 기준으로 정렬하기 때문에 (가중치, 정점) 순서
while (!node_q.empty()) {
int cost = node_q.top().first;
int curr = node_q.top().second;
node_q.pop();
if (dist[curr] < cost) continue;
// 이미 최단 경로라면, 검사할 필요 X
for (int i = 0; i < maps[curr].size(); i++) {
int next = maps[curr][i].first;
// 현재 node에 연결된 다음 node.
int next_cost = cost + maps[curr][i].second;
// 1 ~ 현재 node까지의 가중치 + 다음 node까지의 가중치
if (next_cost < dist[next]) {
// 1 ~ 다음 node까지의 가중치보다 작으면?
dist[next] = next_cost;
// dist 배열의 값을 변경하고
node_q.push({next_cost, next});
// 다음 node 삽입
}
}
}
}
int solution(int N, vector<vector<int>> road, int K) {
int answer = 0;
make_map(road);
init_dist(N);
dijkstra(1);
for (int i = 1; i < N + 1; i++)
if (dist[i] <= K) answer++;
return answer;
}