Dijkstra’s Algorithm

Dijkstra 是根據邊的權重進行比較，用來找節點之間的最小路徑

注意：Dijkstra 演算法無法處理負權重

要點

除了用來儲存圖的二維陣列外
Dijkstra 演算法需要

  1. 距離陣列：起點到每一點的最短距離
  2. 優先佇列：快速尋找當前最短路徑的節點

觀念

從起點開始尋找
如果佇列裡的距離比已知的最短距離還遠，就跳過
遍歷所有與之相連的節點，比較從鎖定後的節點走還是原有的路徑比較短
如果新計算的路徑較短，則更新距離並重新放入佇列裡面

實作

初始化

dis 中，所有點的原距離，初始值設為極大值（除了起點設為 0）
pq 的 first 是距離，second 是節點編號，且排序為從小到大

1
2
vector<int> vis(n), dis(n, 0x3f3f3f3f); // n 為節點樹
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

算法

先將起點放入 pq
並將起點的距離設為 0

1
2
pq.push({0, s});
dis[s] = 0;

接下來進入迴圈，直到所有連通的結點都被走訪為止

1
while (pq.size()) {

先將目前路徑最短的節點取出
檢查該節點是否已經確認為最短距離
如果是就跳過

1
2
auto [d, node] = pq.top(); pq.pop();
if (d > dis[node]) continue;

遍歷所有與目前路徑最短的節點 (node) 連通的節點 (u)
如果從 node 的距離加上從 node 到 u 的距離比目前 (u) 紀錄的最短路徑還小，則使其取代
且將更新過後的節點放入 pq 中

1
2
3
4
5
6
for (auto &[to_idx, to_dis] : g[node]) {
    if (dis[node]+to_dis < dis[to_idx]) {
        dis[to_idx] = dis[node] + to_dis;
        pq.push({dis[to_idx], to_idx});
    }
}}

結果輸出

如果沒有拜訪過該節點，代表起點沒有與該節點連通
否則就輸出距離

1
2
if (!vis[t]) cout << "unreachable\n";
else cout << dis[t] << '\n';

範例

題目：UVA 10986

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long

signed main() { WA();
    int t;
    cin >> t;
    for (int c = 1; c <= t; c++) {
        int n, m, s, t, a, b, w;
        cin >> n >> m >> s >> t;
        vector<vector<pair<int, int>>> g(n);
        while (m--) cin >> a >> b >> w, g[a].push_back({b, w}), g[b].push_back({a, w});

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        vector<int> dis(n, INF);
        q.push({0, s});
        dis[s] = 0;
        while (!q.empty()) {
            auto [d, now] = q.top(); q.pop();
            if (d > dis[now]) continue;

            for (auto &[to_idx, to_dis] : g[now]) {
                if (dis[now] + to_dis < dis[to_idx]) {
                    dis[to_idx] = dis[now] + to_dis;
                    q.push({dis[to_idx], to_idx});
                }
            }
        }

        if (dis[t] == INF) cout << "Case #" << c << ": " << "unreachable\n";
        else cout << "Case #" << c << ": " << dis[t] << '\n';
    }
}

題目：UVA 1112

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f

signed main() {
    int N, I;
    for (cin >> N; N--;) {
        int n, e, t, m;
        cin >> n >> e >> t >> m;
        vector<vector<pair<int, int>>> g(n+1);
        while (m--) {
            int a, b, w;
            cin >> a >> b >> w;
            g[b].push_back({a, w});
        }

        vector<int> dis(n+1, INF);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, e});
        dis[e] = 0;

        while (pq.size()) {
            auto [d, now] = pq.top(); pq.pop();
            if (d > dis[now]) continue;

            for (auto &[to_idx, to_dis] : g[now]) {
                if (dis[now] + to_dis < dis[to_idx]) {
                    dis[to_idx] = dis[now] + to_dis;
                    pq.push({dis[to_idx], to_idx});
                }
            }
        }

        int ans = 0;
        for (auto i : dis) if (i <= t) ans++;
        cout << ans << '\n';
        if (N) cout << '\n';
   }
}