다익스트라 알고리즘이란?
다익스트라는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.
최단 경로 구하는 과정
- 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.
- A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B](가중치)와 d[B]의 값을 비교한다.
- d[A] + P[A][B] < d[B] 라면, d[B] = d[A] + P[A][B]로 갱신시킨다.
- A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
- A의 방문 상태를 TRUE로 바꾼다.
- 방문하지 않은 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드를 다시 A로 지정한다.
- 도착 노드의 방문 상태가 TRUE가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.
다익스트라 알고리즘 예시
출발점 1번 노드의 거리는 0으로, 방문 상태는 TRUE로 설정하고 나머지 노드는 모두 거리 INF, 방문 상태는 FALSE로 초기화한다.
1번 노드에서 갈 수 있는 2번, 3번 6번 노드에서 모두 거리가 INF로 저장되어 있으므로, 각 노드까지의 비용으로 갱신해준다.
1번 노드로부터 거리가 가장 짧은 2번 노드를 방문한다.
2번 노드에서 갈 수 있는 3번, 4번 노드에서 3번 노드는 d[2] + 10 > d[3] 이므로 원래의 값을 유지하고, 4번 노드는 거리가 INF이니 d[2] + 15 = 22로 갱신해준다.
1번 노드로부터 거리가 가장 짧은 3번 노드를 방문한다.
3번 노드에서 방문할 수 있는 4번, 6번 노드에서 4번 노드는 d[3] + 11 < d[4] 이므로 d[3] + 11 = 20으로 갱신해주고, 6번 노드도 d[3] + 2 < d[6] 이므로 d[3] + 2 = 11로 갱신해준다.
1번 노드로부터 가장 거리가 짧은 6번 노드를 방문한다.
6번 노드에서 방문할 수 있는 5번 노드에서 거리가 INF이니 d[6] + 9 = 20으로 갱신해준다. 이때 4번과 5번 모두 거리가 20 이므로 아무 노드나 먼저 방문해도 된다. 나는 5번 노드를 먼저 방문해보겠다.
마지막으로 4번 노드를 방문하면 최단 경로를 구할 수 있다.
다익스트라는 (N - 1)번 탐색 x (최단 거리 정점 찾기(N번 순차탐색)) = O(N^2) 의 시간복잡도를 갖는다.
다익스트라 알고리즘 구현 - C++
위에서 설명한 것을 코드로 구현해보자.
#include<iostream>
#include<vector>
#define INF 1e9
using namespace std;
int V, E, start; //노드 개수, 간선 개수, 시작 노드 번호
vector<pair<int, int> > graph[100001]; // 그래프
bool visited[100001] = { false, }; // 방문 상태
int d[100001]; // 최단 거리
int getSmallestNode() // 방문하지 않은 노드 중에서, 가장 거리가 짧은 노드의 번호를 반환
{
int min_val = INF;
int index = 0;
for (int i = 1; i <= V; i++){
if (d[i] < min_val && !visited[i]){
min_val = d[i]; // 거리가 가장 작은 값
index = i; //노드 번호
}
}
return index;
}
void dijkstra(int start)
{
d[start] = 0;
visited[start] = true;
for (int i = 0; i < graph[start].size(); i++){
int node = graph[start][i].first;
d[node] = graph[start][i].second; // 시작 노드와 연결된 노드의 최단 거리 초기값 세팅
}
for (int i = 0; i < V - 1; i++){
int now = getSmallestNode();
visited[now] = true;
for (int j = 0; j<graph[now].size(); j++){
int cost = d[now] + graph[now][j].second;
if (cost < d[graph[now][j].first]){ // (현재 노드 -> 다음 노드) vs (시작 노드 -> 다음 노드)
d[graph[now][j].first] = cost;
}
}
}
}
int main(){
cin >> V >> E >> start;
for (int i = 0; i < E; i++){
int from, to, cost;
cin >> from >> to >> cost; // from 노드에서 to 노드로 가는 비용 cost
graph[from].push_back({ to, cost });
}
fill_n(d, 100001, INF);
dijkstra(start);
for (int i = 1; i <= V; i++){ //모든 노드의 최단 거리 출력
if (d[i] == INF){
cout << "INFINITY" << '\n';
}
else{
cout << d[i] << '\n';
}
}
return 0;
}
우선순위 큐로 구현하기
우선순위 큐로 구현하게 되면 O(E * logN) (E = 간선의 수, N = 정점의 수) 의 시간복잡도를 갖는다.
#include<iostream>
#include<vector>
#include<queue>
#define INF 1e9
using namespace std;
int V, E, start; //노드 개수, 간선 개수, 시작 노드 번호
vector<pair<int, int> > graph[100001]; // 그래프
int d[100001]; // 최단 거리
void dijkstra(int start){
priority_queue<pair<int, int>>pq;
pq.push({ 0, start }); //시작 노드까지의 최단거리는 0
d[start] = 0;
while (!pq.empty()) {
int dist = -pq.top().first;
int now = pq.top().second;
pq.pop();
if (d[now] < dist)
continue;
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push({ -cost, graph[now][i].first }); // -로 들어가야 큰 순으로 정렬
}
}
}
}
int main(){
cin >> V >> E >> start;
for (int i = 0; i < E; i++){
int from, to, cost;
cin >> from >> to >> cost; // from 노드에서 to 노드로 가는 비용 cost
graph[from].push_back({ to, cost });
}
fill_n(d, 100001, INF);
dijkstra(start);
for (int i = 1; i <= V; i++){ //모든 노드의 최단 거리 출력
if (d[i] == INF){
cout << "INFINITY" << '\n';
}
else{
cout << d[i] << '\n';
}
}
return 0;
}
'알고리즘 > C++' 카테고리의 다른 글
[C++] 문자열 분리하기(split) (0) | 2023.10.14 |
---|---|
[알고리즘] 백트레킹 (0) | 2023.10.05 |
[알고리즘] 이분 탐색 (0) | 2023.10.01 |
[알고리즘] 탐욕(그리디) 알고리즘 (0) | 2021.11.01 |
[알고리즘] 병합 정렬 - C++ (0) | 2021.09.22 |
댓글