다익스트라/데이크스트라 알고리즘
=> 시작점으로부터 나머지 정점들까지의 최단거리를 구하는 알고리즘
길찾기 알고리즘 문제를 해결할때 다익스트라, 플로이드-와샬, A*, 벨만-포드 등을 이용할 수 있습니다.
그중에서 다익스트라(데이크스트라) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 그래프 최단 경로 탐색 알고리즘입니다.
이 알고리즘은 각 노드에 대해 시작 노드에서 해당 노드까지의 최단 경로 길이를 나타내는 “거리” 값을 유지하여 작동합니다.
시작 노드에서 시작하여 0의 거리를 할당하고 다음 각 인접 노드를 방문하여
시작 노드에서 현재 노드를 통해 해당 노드까지의 거리인 임시 거리를 할당합니다.
임시 거리가 해당 노드의 현재 거리보다 작으면 거리가 업데이트됩니다.
그런 다음 알고리즘은 아직 방문하지 않은 거리가 가장 짧은 노드를 선택하고 해당 노드에 대해 프로세스를 반복합니다.
대상 노드를 방문하거나 더 이상 방문하지 않은 노드가 없으면 알고리즘이 종료됩니다.
목적지 노드의 최종 거리 값은 시작 노드에서 목적지 노드까지의 최단 경로의 길이를 나타냅니다.
다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다는 중요한 특징을 가지고 있습니다.
(음수 포함은 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm), 벨만 포드 알고리즘에서 가능)
간단한 예시
시간복잡도
=> O(N^2)/O(V^2+E) => O(NlogN)/O(ElogV)
총 O(N)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고,
현재 노드와 연결된 노드를 매번 일일이 확인하기 때문에 O(N^2)의 시간 복잡도를 가집니다.
코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하이면 일반적으로 풀 수 있습니다.
하지만 노드의 개수가 10,000개를 넘어가는 문제에서는 사용할 수 없습니다.
일반적으로 사용하는 변수명
dist: 그래프의 시작 노드에서 서로 다른 노드까지의 거리를 저장하는 배열 또는 벡터입니다.
이것은 각 노드까지의 임시 거리를 추적하는 데 사용됩니다.
prev: 각 노드에 대한 최단 경로의 이전 노드를 저장하는 배열 또는 벡터.
이것은 알고리즘이 완료되면 최단 경로를 추적하는 데 사용됩니다.
Q: 방문하지 않은 노드를 저장하는 우선순위 큐 또는 세트.
이것은 알고리즘의 각 단계에서 임시 거리가 가장 작은 노드를 효율적으로 선택하는 데 사용됩니다.
u 및 v: 이들은 알고리즘 과정에서 각각 현재 노드와 이웃 노드를 나타내는 데 사용됩니다.
alt: 이 변수는 알고리즘이 노드의 거리를 업데이트할 때 임시 거리를 저장하는 데 사용됩니다.
graph: 이 변수는 그래프를 인접 리스트로 저장하며, 최단 경로를 찾고자 하는 그래프입니다.
s: 이 변수는 시작 노드를 저장하며 최단 경로를 찾으려는 노드입니다.
// 의사코드 Dijkstra 1 function Dijkstra(Graph, source): 2 3 create vertex set Q 4 5 for each vertex v in Graph: // 초기화 6 dist[v] ← INFINITY // 소스에서 v까지의 아직 모르는 길이 7 prev[v] ← UNDEFINED // 소스에서 최적 경로의 이전 꼭짓점 8 add v to Q // 모든 노드는 초기에 Q에 속해있다 (미방문 집합) 9 10 dist[source] ← 0 // 소스에서 소스까지의 길이 11 12 while Q is not empty: 13 u ← vertex in Q with min dist[u] // 최소 거리를 갖는 꼭짓점 14 // 을 가장 먼저 선택한다 15 remove u from Q 16 17 for each neighbor v of u: // v는 여전히 Q에 있다. 18 alt ← dist[u] + length(u, v) 19 if alt < dist[v]: // v 까지의 더 짧은 경로를 찾았을 때 20 dist[v] ← alt 21 prev[v] ← u 22 23 return dist[], prev[] /* 만약 source에서 target까지의 최단 경로만을 구하고 싶다면, 15번째 줄에 u = target을 추가해서 종료시킬 수 있다. 그리고 나서는 source에서 target까지의 최단 경로를 역방향 반복을 통해서 읽을 수 있다 */ 1 S ← empty sequence 2 u ← target 3 while prev[u] is defined: // 스택 S로 최단 경로를 만든다 4 insert u at the beginning of S // 꼭짓점을 스택에 넣는다 5 u ← prev[u] // target에서 source로 이동한다 6 insert u at the beginning of S // source를 스택에 넣는다
C++
const int INF = 1e9;
void Dijkstra(vector<vector<pair<int, int>>> &graph, int s, vector<int> &dist, vector<int> &prev) {
int n = graph.size();
dist.assign(n, INF);
prev.assign(n, -1);
dist[s] = 0;
vector<bool> visited(n, false);
for (int i = 0; i < n; i++) {
int u = -1, minDist = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
if (u == -1) break;
visited[u] = true;
for (auto& [v, w] : graph[u]) {
int alt = dist[u] + w;
if (alt < dist[v]) {
dist[v] = alt;
prev[v] = u;
}
}
}
}
이를 해결하려면 우선순위 큐를 사용한 ‘개선된 다익스트라 알고리즘‘을 사용해야 합니다. => O(NlogN) / O (ElogV)
각 꼭짓점에 대해 O(logN) 시간이 걸리는 우선순위 대기열에서
가장 작은 거리에 있는 꼭짓점을 추출하고 이 작업을 N 번 수행합니다.
알고리즘은 또한 O(logN) 시간이 걸리는 각 정점에 대한 우선순위 큐를 업데이트하며 이 작업도 N 번 수행해야 합니다.
따라서 알고리즘의 전체 시간 복잡도는 O(N log N)입니다.
// 의사코드 개선된 Dijkstra 1 function Dijkstra(Graph, source): 2 dist[source] ← 0 // 초기화 3 4 create vertex set Q 5 6 for each vertex v in Graph: 7 if v ≠ source 8 dist[v] ← INFINITY // 소스에서 v까지의 아직 모르는 길이 9 prev[v] ← UNDEFINED // v의 이전 노드 10 11 Q.add_with_priority(v, dist[v]) 12 13 14 while Q is not empty: // 메인 루프 15 u ← Q.extract_min() // 최고의 꼭짓점을 제거하고 반환한다 16 for each neighbor v of u: // Q에 여전히 남아 있는 v에 대해서만 17 alt ← dist[u] + length(u, v) 18 if alt < dist[v] 19 dist[v] ← alt 20 prev[v] ← u 21 Q.decrease_priority(v, alt) 22 23 return dist, prev
C++
const int INF = 1e9;
void Dijkstra(vector<vector<pair<int, int>>> &graph, int s, vector<int> &dist, vector<int> &prev) {
int n = graph.size();
dist.assign(n, INF);
prev.assign(n, -1);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
Q.push({0, s});
while (!Q.empty()) {
int u = Q.top().second;
Q.pop();
for (auto& [v, w] : graph[u]) {
int alt = dist[u] + w;
if (alt < dist[v]) {
dist[v] = alt;
prev[v] = u;
Q.push({dist[v], v});
}
}
}
}
정점의 수가 적거나 간선의 수가 매우 많은 경우에는 아예 우선순위 큐를 사용하지 않고 구현하는 방식이 더욱 빠른 경우가 있습니다.
ex) 다익스트라 알고리즘 코드 (백준 18352)
https://www.acmicpc.net/problem/18352
#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;
constexpr int INF = INT32_MAX;
constexpr int MAXN = 300001;
// 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
int N, M, K, X;
list<int> myList;
/*
각 노드에 연결되어 있는 노드에 대한 정보를 담는 벡터
a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
*/
vector< pair<int, int> > graph[MAXN];
// 그래프의 시작 노드에서 서로의 노드까지의 거리를 저장하는 배열
// 이것은 각 노드에 대한 임시 거리를 추적하는 데 사용됩니다.
// 임시 노드
int dist[MAXN];
// 우선 순위 큐는
// 임시 거리를 가진 노드를 효율적으로 선택하는 데 사용
// <거리, 노드 인덱스>
priority_queue<pair<int, int>> myPQ;
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
// 정점의 개수 N, 간선의 개수 M, 간선의 정보 K, 출발 정점의 번호 X
cin >> N >> M >> K >> X;
// 모든 도로의 정보를 입력받기
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
// A -> B : C
graph[A].push_back({ B, 1 });
}
// 임시 노드를 모두 무한으로 초기화
fill(dist, dist + MAXN, INF);
// 우선순위 큐에 삽입.
myPQ.push({ 0, X }); // < first : 거리 , second : 노드 인덱스 >
dist[X] = 0; // 시작 노드 가기위한 최단 경로는 0으로 설정
while (!myPQ.empty()) {
// -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
// (최소힙으로 구현)
int nCost = -myPQ.top().first;
int now = myPQ.top().second;
myPQ.pop();
// 해당 노드에서 연결된 모든 경로를 확인
for (int i = 0; i < graph[now].size(); i++) {
// 0이라면 길이 없다는 의미 continue
if (graph[now][i].second == 0) continue;
// disSum = 임시 노드 + 현재 노드에서 i로가는 비용
int disSum = nCost + graph[now][i].second;
// 비용이 더 작다면 최단경로 테이블 값을 갱신.
if (disSum < dist[graph[now][i].first]) {
// 임시 노드 업데이트
dist[graph[now][i].first] = disSum;
// 우선순위 큐에 (거리, 노드 인덱스) 푸시
myPQ.push(make_pair(-disSum, graph[now][i].first));
}
}
}
// 문제에서 원하는 답을 출력하는 부분
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (dist[i] == K) {
myList.push_back(i);
cnt++;
}
}
if (cnt == 0) cout << -1;
else
{
myList.sort();
for (auto it = myList.begin(); it != myList.end(); it++)
cout << *it << "\n";
}
return 0;
}
참고) Dijkstra와 A* 의 차이점
목표점
Dijkstra는 시작점에서 나머지 정점들까지의 최단거리를 구하는 알고리즘
A*는 시작점과 목표점이 정해지면 두 점의 최단거리를 구하는 알고리즘
노드를 결정하는 방법
Dijkstra는 우선순위 큐를 사용하여 알고리즘의 각 단계에서 임시 거리가 가장 작은 노드를 효율적으로 선택
A*는 노드에서 목표까지 남은 거리를 추정하기 위해 휴리스틱 함수를 사용하는 Dijkstra 알고리즘의 확장
검색 공간의 많은 부분을 정리할 수 있으며 Dijkstra 알고리즘보다 더 효율적으로 최단 경로를 찾을 수 있음
남은 거리
Dijkstra 알고리즘은 시작점에서 각 정점에 이르는 최단 거리만을 고려. 목적 정점이 없기에 남은 거리를 구할 수 없음
A* 는 남은 거리를 고려함
최적 경로
Dijkstra 는 임의의 시작점으로부터 시작하여 모든 정점을 탐색. 최적 경로 보장하지 않습니다.
(이를 해결하기 위해 모든 정점을 시작점으로 가지는 플로이드와샬 알고리즘이다 있다. 하지만 정점의 개수만큼 시간 비용이 증가)
A* 는 시작 지점부터 목표지점까지의 휴리스틱 함수를 통해 추정하여 점수를 매기고,
그 점수를 바탕으로 빠른 탐색을 한다. 최적 경로의 근삿값을 보장합니다.
상황에 따른 선택
하나의 정점에서부터 다른 하나의 정점까지의 최단 경로를 구하는 경우 => A*
하나의 정점에서부터 다른 모두의 정점까지 최단 경로를 구하는 경우 => Dijkstra
하나의 목적지로 가는 모든 최단 경로를 구하는 문제 => Floyd-Warshall
모든 최단 경로를 구하는 문제 => Floyd-Warshall
참조
https://hyo-ue4study.tistory.com/195
Let me introduce a massage to recover your tired body from your trip to Manila.
핑백: 알고리즘 - 벨만-포드 (Bellman–Ford Algorithm) 알고리즘 정리 - 어제와 내일의 나 그 사이의 이야기
핑백: 백준 1753번 (최단경로, C++, Dijkstra) [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기
핑백: 백준 1446번 (지름길, C++, Dijkstra) [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기
핑백: 백준 18352번 (특정 거리의 도시 찾기, C++, Dijkstra) / 추가 반례 [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기