[Computer Algorithms] Dijkstra's Algorithm (데이크스트라의 알고리즘)

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 무한대로 초기화한다. (출발 노드는 0으로 초기화)

3. 간선을 출발지, 도착지, 가중치 순서로 입력한다

4. 출발 노드의 거리와 노드 번호를 우선순위 큐에 넣는다.

5. 우선순위 큐의 최상위 노드를 선택한다. (최단 거리가 가장 짧은 노드)

6. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.

7. 갱신된 노드의 거리와 노드 번호를 우선순위 큐에 넣는다.

8. 우선순위 큐가 Empty한 상태가 될 때 까지 5 ~ 7을 반복한다.

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;

int N, M;                                                                           // N: 노드의 개수, M: 간선의 개수
int start;                                                                          // start: 시작 노드의 번호
vector<pair<int, int>> graph[100];                                                  // 그래프
vector<int> dist(100);                                                              // 최단 거리 테이블
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 우선순위 큐(거리, 노드 번호)

void input()
{
    cin >> N >> M;
    cin >> start;

    fill(dist.begin(), dist.end(), INT_MAX);
    dist[start] = 0;

    for (int i = 0; i < M; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from].push_back(make_pair(to, weight));
    }
}

void dijkstra()
{
    pq.push(make_pair(dist[start], start));
    while (!pq.empty())
    {
        int cur_dist = pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();

	// dist 테이블에 갱신되어 있는 것이 최신 값인데, 테이블에 있는 값이 더 작다면 pass
        if (dist[cur_node] < cur_dist)
            continue;

        for (auto next : graph[cur_node])
        {
            if (dist[next.first] > dist[cur_node] + next.second)
            {
                dist[next.first] = dist[cur_node] + next.second;
                pq.push(make_pair(dist[next.first], next.first));
            }
        }
    }
}

void print_dist()
{
    for (int i = 1; i <= N; i++)
    {
        cout << "node " << i << " : " << dist[i] << endl;
    }
}

int main(void)
{
    input();
    dijkstra();
    print_dist();

    return 0;
}

 

우선순위 큐 구현 방식	삽입 시간	삭제 시간
배열(Array), 리스트(List)	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

힙을 사용한 우선순위 큐를 사용하면 O(V^2) -> O(ElogV)로 시간 복잡도를 줄일 수 있다.