23. 다익스트라

다익스트라

빠른 설명

다익스트라 알고리즘은 간선 가중치가 음수가 아닐 때, 한 시작점에서 모든 정점까지의 최단거리를 구한다.

언제 쓰는가

• 도로망 최단거리
• 가중치가 있는 그래프의 최단 경로
• 모든 간선 가중치가 $0$ 이상일 때

시간복잡도

• 우선순위 큐 사용: $O((V+E)\log V)$

주의

• 음수 간선이 있으면 일반 다익스트라는 사용할 수 없다.
• 음수 간선이 있으면 벨만포드를 고려한다.

참고자료

• CP-Algorithms - Dijkstra
• Wikipedia - Dijkstra’s algorithm
• GeeksforGeeks - Dijkstra’s Shortest Path Algorithm
• 나무위키 - 다익스트라 알고리즘

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
const long long INF = (1LL << 60);
 
int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);
 
    graph[0].push_back({1, 2}); // cost, node
    graph[0].push_back({2, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 2});
    graph[2].push_back({3, 3});
    graph[3].push_back({4, 1});
 
    vector<long long> dist(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
 
    dist[0] = 0;
    pq.push({0, 0});
 
    while (!pq.empty()) {
        auto [cost, cur] = pq.top();
        pq.pop();
 
        if (cost != dist[cur]) continue;
 
        for (auto [next, weight] : graph[cur]) {
            if (dist[next] > cost + weight) {
                dist[next] = cost + weight;
                pq.push({dist[next], next});
            }
        }
    }
 
    for (long long d : dist) cout << d << ' ';
}

Python 코드

import heapq
 
INF = 10**18
n = 5
graph = [[] for _ in range(n)]
 
graph[0].append((1, 2))
graph[0].append((2, 5))
graph[1].append((2, 1))
graph[1].append((3, 2))
graph[2].append((3, 3))
graph[3].append((4, 1))
 
dist = [INF] * n
dist[0] = 0
pq = [(0, 0)]
 
while pq:
    cost, cur = heapq.heappop(pq)
    if cost != dist[cur]:
        continue
 
    for nxt, weight in graph[cur]:
        if dist[nxt] > cost + weight:
            dist[nxt] = cost + weight
            heapq.heappush(pq, (dist[nxt], nxt))
 
print(dist)