C++ 다익스트라 개념과 예제-백준 1753번

다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다.

다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다.

1 -> (2,8) (3,3)
2 -> (4,4) (5,15)
3 -> (4,13)
4 -> (5,2)
5

위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다.
정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.)

1	2	3	4	5
0	INF	INF	INF	INF

그 중 거리가 가장 짧은 1을 채택해서 탐색합니다.

---

1	2	3	4	5
0	8	3	INF	INF

1은 이제 탐색했으므로 방문여부 체크하고 다시 탐색하지 않습니다. 1을 제외한 노드들 중 거리가 짧은 3을 우선적으로 탐색합니다.

---

1	2	3	4	5
0	8	3	3+13	INF

3을 거쳐서 4를 가는 것이므로 13을 더해줍니다.
남아 있는 노드들 중 2가 거리가 작으므로 2를 탐색합니다.

---

1	2	3	4	5
0	8	3	16 / 8+4 = 12	23

2를 탐색했을때 (4,4)이므로 1->2->4 를 거치게 되면 8+4= 12가 됩니다.
그러나 기존에 16이란 값이 있는데, 더 작은 값을 채택해서 12로 결정합니다.
방문하지 않은 노드들 중에서 거리가 12가 가장 낮으므로 4를 탐색합니다.

---

1	2	3	4	5
0	8	3	12	23 / 12 + 5

(5,5) 이므로 12 + 5 해서 17이 되므로 더 작은 17이 체택됩니다.
이런식으로 5까지 탐색해서 모든 노드의 방문을 마치면 최단거리 탐색이 끝납니다.

---

예제로 확인하기

최단경로 (백준 1753)

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 1

0
2
3
7
INF

---

C++ 코드

거리가 가장 작은 노드를 골라서 탐색해야되는데, 거리가 작은 노드를 고르는게 시간 복잡도가 큽니다.
그러므로 우선순위 큐를 사용합니다.

우선순위큐는 pair에서 첫번째 요소가 큰 순서대로 나오므로, (-1 * 총거리, 노드) 형식으로 저장해서 총 거리가 작은 순서대로 나오도록 합니다.

#include <iostream>
#include <queue>
#include <vector>
#define INF 987654321
#define endl "\n" // 매우 중요!!!!

using namespace std;

int V, E, k;
vector<int> dist;
// (다음노드, 거리)
vector<vector<pair<int, int>>> adjacnet;


void dijkstra() {
    // (총거리, 노드) 최소우선순위큐
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, k));
    dist[k] = 0;

    while (!PQ.empty()) {
        int distance = -PQ.top().first;
        int node = PQ.top().second;
        PQ.pop();

        if (dist[node] < distance) continue;

        for (int i = 0; i < adjacnet[node].size(); i++) {
            int next = adjacnet[node][i].first;
            int newDistance = adjacnet[node][i].second;

            // 새로 최단 거리 발견시
            if (dist[next] > distance + newDistance) {
                dist[next] = distance + newDistance;
                PQ.push(make_pair(-dist[next], next));
            }
        }
    }
}


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> V >> E >> k;
    adjacnet.resize(V + 1);
    dist.resize(V + 1, INF);
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adjacnet[a].push_back(make_pair(b, c));
    }

    dijkstra();

    for (int i = 1; i <= V; i++) {
        if (dist[i] == INF)
            cout << "INF" << endl;
        else
            cout << dist[i] << endl;
    }

    return 0;
}