[알고리즘] 다익스트라 (Dijkstra)

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 | 큰돌 - 인프런

참고 강의

 

1. 개요

---

오늘 공부해볼 알고리즘은 다익스트라 알고리즘입니다.

 

다익스트라 알고리즘은 가중치가 양수인 그래프에서 한가지 시작지점에서 모든 노드까지의 최단 경로를 찾는 알고리즘 입니다.

 

가중치가 음수가 되면 알고리즘에 문제가 생기게 됩니다. (이 경우엔 벨먼-포드 알고리즘 사용)

 

또한 우선순위 큐(priority queue)를 활용해서 처리하지 않은 정점들 중에서 거리가 가장 짧은 정점을 찾게 됩니다.

 

이 개념을 바탕으로 운송 시스템, 네비게이션등 우리 일상에서도 다양하게 활용되는 알고리즘 중 하나입니다.

 

핵심 특징

• 단일 출발점 최단 경로 문제(Single Source Shortest Path) 해결
• 음수 가중치가 없는 그래프에서만 사용 가능
• 방향 그래프, 무방향 그래프 모두 적용 가능
• 그리디(탐욕적) 알고리즘의 대표적인 예시

그래프 용어

• 정점(Vertex/Node): 그래프의 각 지점
• 간선(Edge): 정점들을 연결하는 선
• 가중치(Weight): 각 간선에 부여된 비용이나 거리
• 경로(Path): 한 정점에서 다른 정점까지 가는 간선들의 연속

---

 

2. 설명

---

우선 손으로 하나씩 쓰며 전체적인 흐름을 느껴보겠습니다.

역시 알고리즘은 손으로 써보는게 참맛입니다.

 

글로만 쓰여있는 알고리즘 설명을 보면 솔직히 한눈에 이해하기가 매우 어렵습니다.

 

이런식으로 손으로 한번 써본뒤 글을 보게 되면 이해가 갑자기 잘되는 마법이 일어납니다.

 

1. 시작 노드의 거리를 0으로, 나머지는 무한대로 초기화

2. 시작 노드를 우선순위 큐에 넣음

3. 큐에서 가장 가까운 노드를 꺼냄 (우선 순위 큐 비교함수 Greater사용 )
기본 priority_queue는 큰 값이 우선 (max heap)
greater 사용으로 작은 값이 우선 (min heap)으로 변경 → 거리가 짧은 노드부터 처리하기 위함

4. 그 노드의 인접노드들을 순회하며 거리 체크

5. 이전 거리보다 가까우면 거리를 update

6. update한 경우 priority queue에 push

7. 큐가 빌 때까지 3번부터 반복

 

 

#include <bits/stdc++.h> 
using namespace std; 
const int INF = 1e9; // 무한대 값 설정 
vector<pair<int, int>> adj[20004]; // 그래프의 인접 리스트 표현   
vector<int> dist(20004, INF); // 최단 거리 배열 
void dijkstra(int start) { 
priority_queue<pair<int, int>, vector<pair<int, int>>, 
greater<pair<int, int>>> pq; 
dist[start] = 0; 
pq.push({0, start}); 

    while (!pq.empty()) { 
        int here_cost = pq.top().first; 
        int u = pq.top().second; 
        pq.pop(); 
 
        // 느긋한 삭제 
        if (dist[u] != here_cost) continue; 
 
        for (auto &[v, weight] : adj[u]) { 
            int new_cost = here_cost + weight; 
            if (new_cost < dist[v]) { 
                dist[v] = new_cost; 
                pq.push({new_cost, v}); 
            } 
        } 
    } 
} 
 
int main() { 
    int n, m, start; 
    cin >> n >> m >> start; 
 
    for (int i = 0; i < m; i++) { 
        int u, v, w; 
        cin >> u >> v >> w; 
        adj[u].push_back({v, w}); 
    } 
 
    dijkstra(start); 
 
    for (int i = 1; i <= n; i++) { 
        if (dist[i] == INF) cout << "INF\n"; 
        else cout << dist[i] << "\n"; 
    } 
 
    return 0; 
}

 

마지막으로 한가지 더 언급할 점은 바로 느긋한 삭제입니다.

 

이 코드는 특정 노드에 대해 우선순위 큐에 거리가 여러번 등록되는 경우를 최적화 하기 위함입니다.

• dist[u]: 현재까지 발견한 진짜 최단거리 
• here_cost: 큐에서 꺼낸 예전에 저장했던 거리

만약 둘이 다르다면? → 큐에 있던 건 이미 더 좋은 경로로 갱신된 후의 구버전이라는 뜻

 

"큐에서 꺼낸 거리가 현재 최단거리와 다르면 구버전이니까 연산을 추가로 하지 않고 넘어가자는 의미입니다."

---

 

3. 시간 복잡도

---

시간복잡도는 ElogE 또는 ElogV입니다.

 

최악의 경우 모든 간선에 대해 우선위큐에 집어넣어야 하며

 

이 때 E개의 간선에 대해 우선순위큐를 기반으로 최단거리 정점 추출에 logE가 들어 ElogE가 됩니다.

 

여기서 E는 방향성이 있는 완전그래프에서 E = V(V - 1)라는 특징을 가집니다.

 

이 때문에 ElogV^2 가 되고 이는 2ElogV가 되어 ElogV가 됩니다.