Priority queue를 이용한 Dijkstra

Dijkstra alogrithm

가중 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

특징

• 음수 가중치를 허용하지 않음
• 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택하여 인접한 정점들의 거리를 갱신
  • 정점 번호 순이 아니라 현재까지의 최단 거리가 확정된 순서로 정점을 처리
  • 정점 번호 순으로 처리한다면 비용이 더 적은 경로가 나중에 나타날 수 있음

동작 원리

1. 시작 정점을 최단 거리 0 으로 설정하고, 나머지 정점과의 최단 거리를 INF(무한대)로 설정
2. 현재 방문할 정점을 선택
3. 해당 정점과 인접한 정점들의 거리를 갱신
4. 모든 정점에 대해 위 과정을 반복

핵심 연산

• 최소 거리 정점 선택 → 현재 방문하지 않은 정점 중 가장 최단 거리가 작은 정점을 선택
• 거리 갱신 → 선택된 정점을 기준으로 인접한 정점들의 거리를 업데이트

자료구조와 연산

• array, list 등을 사용하여 찾으면 O(V)의 시간이 소요
• priority_queue를 활활용하면 O(log V)로 줄일 수 있음

시간 복잡도

정점(vertex)의 수 V, 간선(edge)의 수 E로 할 때 각 자료구조 별 시간 복잡도는 아래와 같음

사용된 자료구조	최소 거리 정점 선택	거리 갱신	전체 시간 복잡도
우선순위 큐	O(E log V)	O(E log V)	O(E log V)
배열	O(V²)	O(E)	O(V² + E) ≈ O(V²)

시간 복잡도 (우선순위 큐)

priority_queue(최소 힙)를 사용하면 오름차순(작은 값 → 큰 값)으로 정렬

1. 최소 거리 정점 선택
   • top() 으로 최소 거리를 가진 정점을 O(1) 에 가져올 수 있음
   • pop() 의 시간 복잡도는 O(log V) 이므로 빠르게 삭제 가능
   • 시간 복잡도: priority queue에 삽입되는 원소의 수는 edge에 비례할 수 있음 → O(E log V)
2. 거리 갱신
   • 거리 값이 갱신되면 push() 를 이용하여 새로운 값 삽입 → O(log V)
   • 시간 복잡도: 모든 edge에 대하여 발생할 경우 O(E log V)
3. 전체 시간 복잡도
   • O(E log V) + O(E log V) = O(E log V)

시간 복잡도 (배열)

1. 최소 거리 정점 선택
   • 최단 거리 노드를 찾는 작업에 모든 정점 탐색 필요 → O(V)
   • 시간 복잡도: 모든 vertex에 대하여 계산 → O(V²)
2. 거리 갱신
   • 선택된 정점에서 인접한 간선들을 모두 확인
   • 시간 복잡도: 모든 edge에 대하여 계산 → O(E)
3. 전체 시간 복잡도
   • O(V² + E) ≈ O(V²)

구현

C++을 이용하여 예시 코드를 작성하였다. 아래 링크에서 전체를 확인할 수 있다.

https://github.com/grade-e/dijkstra-pq-container

코드

Node

struct Node {
    int id;                                    // vertex number(id)
    int cost;                                  // cost to reach the vertex
    bool operator>(const Node& other) const {  // for min-heap
        return this->cost > other.cost;
    }
};

Dijkstra

vector<int> dijkstra(int start, int nVertex, vector<vector<Node>>& graph) {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    vector<int> costs(nVertex, INF);
    costs[start] = 0;
    pq.push({start, 0});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int id = cur.id;
        int cost = cur.cost;

        // Skip if we have already found a better path
        if (cost > costs[id]) continue;

        // Traverse all neighbors
        for (const Node& neighbor : graph[id]) {
            int nid = neighbor.id;
            int ncost = neighbor.cost;
            int new_cost = costs[id] + ncost;

            // Update the cost if we have found a better path
            if (new_cost < costs[nid]) {
                costs[nid] = new_cost;
                pq.push({nid, new_cost});
            }
        }
    }
    return costs;
}

main

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

#include "dijkstra.hpp"

using namespace std;

int main() {
    int n = 5;      // number of vertices
    int start = 0;  // starting vertex

    vector<vector<Node>> graph(n);  // adjacency list
    graph[0].push_back({1, 10});    // 0 → 1, 10
    graph[0].push_back({3, 30});    // 0 → 3, 30
    graph[0].push_back({4, 100});   // 0 → 4, 100
    graph[1].push_back({2, 50});    // 1 → 2, 50
    graph[2].push_back({4, 10});    // 2 → 4, 10
    graph[3].push_back({2, 20});    // 3 → 2, 20
    graph[3].push_back({4, 60});    // 3 → 4, 60
    vector<int> shortest_paths = dijkstra(start, n, graph);

    cout << "Shortest distances from vertex " << start << ":\n";
    for (int i = 0; i < n; ++i) {
        if (shortest_paths[i] == std::numeric_limits<int>::max()) {
            cout << "Vertex " << i << ": INF\n";
        } else {
            cout << "Vertex " << i << ": " << shortest_paths[i] << "\n";
        }
    }
    return 0;
}

그래프

예시를 그림으로 표현하면 아래와 같음

graph TD;
    A((0)) -->|10| B((1));
    A((0)) -->|30| D((3));
    A((0)) -->|100| E((4));
    B((1)) -->|50| C((2));
    D((3)) -->|20| C((2));
    D((3)) -->|60| E((4));
    C((2)) -->|10| E((4));

탐색 과정

• 다익스트라 알고리즘은 우선순위 큐를 사용해 “가장 짧은 거리를 가진” 정점을 먼저 처리
• 처리 순서는 최단 경로가 확정되는 순서

단계 별 탐색과정

단계	정점	거리 테이블	설명
Step 0	-	[0, INF, INF, INF, INF]	시작 정점 0의 거리를 0으로 설정
Step 1	0	[0, 10, INF, 30, 100]	정점 0에서 인접 정점 갱신: 0→1: 10, 0→3: 30, 0→4: 100
Step 2	1	[0, 10, 60, 30, 100]	정점 1 처리 (현재 최소 비용 10): 1→2: 10+50 = 60 으로 정점 2 갱신
Step 3	3	[0, 10, 50, 30, 90]	정점 3 처리 (현재 최소 비용 30): 3→2: 30+20 = 50 (정점 2 갱신), 3→4: 30+60 = 90 (정점 4 갱신)
Step 4	2	[0, 10, 50, 30, 60]	정점 2 처리 (현재 최소 비용 50): 2→4: 50+10 = 60 (정점 4 갱신: 90에서 60으로 변경)
Step 5	4	[0, 10, 50, 30, 60]	정점 4 처리 (현재 최소 비용 60): 더 이상의 갱신 없음

결과 그래프

flowchart TD
    A0["0 (0)"] -->|10| A1["1 (10)"]
    A0 -->|30| A3["3 (30)"]
    A0 -->|100| A4["4 (100)"]
    A1 -->|50| A2["2 (60)"]
    A3 -->|20| A2["2 (50)"]
    A3 -->|60| A4["4 (90)"]
    A2 -->|10| A4["4 (60)"]

프로그램 실행 결과

Vertex 0: 0
Vertex 1: 10
Vertex 2: 50
Vertex 3: 30
Vertex 4: 60