解決案例 #
假設給一張這樣的 graph ，可以用鄰接矩陣表示 : Dijkstra Algorithm 就是給一個點，輸出這個點到所有節點的最短距離 ; 以下面的 Graph 為例，給一個節點 A ，Dijkstra Algorithm 可以輸出 A 到 B、C、D 的最短距離。
Graph :
7
A -------- B
| /|
2| 3/ |1
| / |
C -------- D
4
鄰接矩陣
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 7 | 2 | -1 |
| B | 7 | 0 | 3 | 1 |
| C | 2 | 3 | 0 | 4 |
| D | -1 | 2 | 5 | 0 |
接下來用上面的 Graph 示範整個 Dijkstra Algorithm 的流程
第 0 步 #
假設要找點 A 到每個點的最短距離
先建一個長的像這樣子的表: 意思是
- A 到 A 的距離是 0
- A 到 B 的距離是無限大
- A 到 C 的距離是無限大
- A 到 D 的距離是無限大
這裡的無限大在之後填表的過程會被數字給替代
已訪問 : 裡面放布林值，代表這個節點已被看過 前驅節點 : 用來記錄這個點是從哪裡來的
| 節點 | 距離 | 已訪問 | 前驅節點 |
|---|---|---|---|
| A | 0 | x | - |
| B | ∞ | x | - |
| C | ∞ | x | - |
| D | ∞ | x | - |
第 1 步 #
我們先看 A，並把 A 標記成 “已訪問” 觀察一下 Graph，A 和 B 以及 C 相鄰，距離分別是 7 和 2，那我們就把 7 和 2 填上表格。 然後將 B 和 C 的前驅節點填上 A，代表 B 和 C 是從 A 過來的。
| 節點 | 距離 | 已訪問 | 前驅節點 |
|---|---|---|---|
| A | 0 | ✓ | - |
| B | 7 | x | A |
| C | 2 | x | A |
| D | ∞ | x | - |
第 2 步 #
看完 A 了，接下來要看誰呢 ? 我們來找一下此時距離最小的那位。還記的前面把 A 標記成"已訪問“嗎 ? 因為 A 已經看過了，所以這個時候會排除掉 A，從 B、C、D 中找到距離最小的，最小的是誰 ? 是 C ! 所以接下來看C。 接著 :
- 把 C 標記成已訪問
- 找一下 C 和誰相鄰 ? C 和 A、B、D相鄰，但 A 已經被訪問過，所以過濾掉 A。接下來是關鍵步驟，以 C 到 B 為例子 : 比較一下 C 目前的距離 (也就是 2)+ C 到 B 的距離 (3) 會不會比現在表格上 B 的距離還短 (7)，答案是會，因為 2 + 3 = 5 比 7 還小，那就把現在的 7 替換成 5 ，B 的前驅節點改成 C。
- 如果還是不懂，比較直白的意思是 A -> C -> B 的距離會比 A -> B 的距離還小，所以 B 的最短距離要更新成 A -> C -> B 的距離，並且因為 B 變成從 C 過來的，所以前驅節點要改成 C。
- 了解上面 C 到 B 的例子後，看看 C 到 D，C 到 D 的距離是 4，但記的加上目前 C 的距離 2，所以是 2 + 4 = 6 (也就是 A -> C -> D 的加總距離) ，檢查有沒有比現在 D 的距離小，因為 D 的距離是無限大，所以肯定有~因此更新 6 上去，前驅節點改為 C
PS : 已訪問也有那個節點的距離已經確定是最短距離，未來不會被變更的含意
| 節點 | 距離 | 已訪問 | 前驅節點 |
|---|---|---|---|
| A | 0 | ✓ | - |
| B | 5 | x | C |
| C | 2 | ✓ | A |
| D | 6 | x | C |
第 3 步 #
- 剩 B 和 D 未被訪問( 可以理解成 B 和 D 還沒有找到最短距離 )，從 B 和 D 找距離小的 : 找到 B，將 B 標記為已訪問 (代表 B 的距離被確認為最短距離)。
- 看一下 B 和誰相鄰？有 A、C、D ，但 A 、C 已經被訪問過了，所以實際上只要看 D
- 目前 B 的距離 (5) + B 到 D 的距離 (1) 是 6，和目前 D 的距離一樣，所以不更新 (當然要更新也行，變成另一種最短路徑的可能)
| 節點 | 距離 | 已訪問 | 前驅節點 |
|---|---|---|---|
| A | 0 | ✓ | - |
| B | 5 | ✓ | C |
| C | 2 | ✓ | A |
| D | 6 | x | C |
PS : 這裡的最短距離指的是從 A 到某節點的最短距離
第 4 步 #
- 剩下 D 還未被訪問，標記 D 為已訪問，但因為除了 D 以外的節點都被訪問過了，所以到這此結束
| 節點 | 距離 | 已訪問 | 前驅節點 |
|---|---|---|---|
| A | 0 | ✓ | - |
| B | 5 | ✓ | C |
| C | 2 | ✓ | A |
| D | 6 | ✓ | C |
怎麼看 ? #
經過前面的流程後，產生了下面⬇這張表格，要如何看這張表呢 ? 這張表需要注意的有「距離」和「前驅節點」
| 節點 | 距離 | 已訪問 | 前驅節點 |
|---|---|---|---|
| A | 0 | ✓ | - |
| B | 5 | ✓ | C |
| C | 2 | ✓ | A |
| D | 6 | ✓ | C |
首先，注意到「距離」，這裡的距離指的是 A 到 X 點的最短距離，比如
- A 到 B 的最短距離是 5
- A 到 C 的最短距離是 2 再來看到「前驅節點」，「前驅節點」可以知道這個點是從哪一個點過來的，比如
- D 是從 C 過來的
- C 是從 A 過來的
- 所以 A 到 D 的最短路徑是 A -> C -> D
總結 #
總結上面的步驟
- 第一步 : 建好初始化表格，起點到起點填 0，其他填無限大
- 第二步 : 把起點標記成已訪問，找到起點到鄰居的距離，並記在表格上
- 第三步 : 找到當前表格上未被訪問且距離最小的節點，假設這個點叫 X 好了
- 第四步 : 檢查 X 的鄰居，比如 X 其中一個鄰居叫 Y 好了，看看 「X 的距離」 + 「X 到 Y 的距離」會不會比 「Y 的距離 小 」? 若會的話就拿 「X 的距離 + X 到 Y 的距離」替換掉 「Y 的距離」 ，並且 Y 的前驅節點設定為 X ; 不會的話則什麼不動。
- 重複第三、四步，直到所有節點都被訪問過
PS : 公式
距離[當前節點] + 邊權重 < 距離[鄰居]
程式 #
PS : 此程式由 Claude 產生，讚美 Claude ✨
第 0 步 #
先做一些定義
裡面比較複雜的應該是「定義無限大」那塊，實在不行其實設定 INF = 999999999 也行 (看題目測資範圍給多大) ; 還記得剛開始建表的時候要填「無限大」嗎，到時候建表時就會用到它😎。
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <utility>
#include <functional>
// 定義無限大
const int INF = numeric_limits<int>::max();
// 邊的結構 (目標節點, 權重)
typedef pair<int, int> Edge;
// priority_queue 中的元素 (距離, 節點)
typedef pair<int, int> Node;
PS : priority_queue 是一種丟資料進去會自動排列 (C++ 預設由小排到大) 的資料結構，也有人把它稱為「堆積 ( heap )」
第 1 步 #
Claude 把 Graph 寫成一個類別，private 的部分有總節點數 V，和一個二維陣列 adj 作為鄰接表的角色。
解釋一下 vector<vector<Edge>> 這個看起來很可怕的東西，我們一層一層看 :
- 最內層的
vector<Edge>，Edge是一個資料型態，我們在第 0 步時定義了它 ，Edge包含了「節點」和「權重」，vector<Edge>就是一個用來裝Edge這種資料型態的陣列。 vector<vector<Edge>>，其實就只是把前面的vector<Edge>放到另一個陣列裡變成二維陣列，你可以想成它是一個二維陣列，每一格都是一個Edge這種資料型態的變數。
class Graph {
private:
int V; // 節點數量
vector<vector<Edge>> adj; // 鄰接表
}
第 2 步 #
public 的部分
-
建構函數
Graph(int):Graph(int)接收一個傳入參數 :vertices，並把前面宣告的私有變數V設定為vertices- 使用
resize將adj的大小設定為V( 意思是有V列，每列會是一個vector<Edge>)
-
void addEdge(int,int,int):- 傳入兩個節點 : u 和 v，代表這兩個點是鄰居，同時傳入他們間的權重 : weight
- 接著是
adj[u].push_back({v, weight});可以看一下程式下方的「Graph A」和「鄰接表 A」會比較清楚，addEdge()的目的就是要產生「鄰接表 A」。 - 這裡以「鄰接表 A」為例，它代表 :
- A 和 B 是鄰居，彼此的權重是 7
- A 和 C 是鄰居，彼此的權重是 2
- B 和 A 是鄰居，彼此的權重是 7 . . .
- 然後因為 Graph A 是無向圖，所以在
adj[u].push_back({v, weight});時也要順便adj[v].push_back({u, weight});
PS : 無向圖就是指沒有方向性，兩個節點可以雙向溝通。如果是有向圖就有方向性，有向圖舉例 : A 節點可以直接到 B 節點，但 B 節點不能直接到 A 節點 （強調一下是直接，而不是間接）
class Graph {
private:
int V; // 節點數量
vector<vector<Edge>> adj; // 鄰接表
public:
Graph(int vertices) {
V = vertices;
adj.resize(V);
}
// 添加邊 (無向圖)
void addEdge(int u, int v, int weight) {
adj[u].push_back({v, weight});
adj[v].push_back({u, weight}); // 若為有向圖，移除此行
}
}
Graph A :
7
A -------- B
| /|
2| 3/ |1
| / |
C -------- D
4
鄰接表 A :
| 0 | 1 | 2 | |
|---|---|---|---|
| A | (B,7) | (C,2) | - |
| B | (A,7) | (C,3) | (D,1) |
| C | (A,2) | (B,3) | (D,4) |
| D | (B,1) | (C,4) | - |
PS : 程式的節點是寫成
int，這裡為了方便演示用 A、B、C、D 表示節點
第 3 步 #
註 : 這裡挑重點程式介紹😊
vector<int> dijkstra(int): 這是 Dijkstra 的核心程式，傳入參數有int src，代表要拿哪個節點當起點 ( 以前面的例子src會是節點 A )。priority_queue<Node, vector<Node>, greater<Node>> pq， 可以參考下面C++priority_queue的參數意義 :Node( 第一參數 ) : 代表priority_queue儲存的資料型態，這裡的 Node 是我們自訂的資料型態，Node是pair<int,int>的代表vector<Node>(第二個參數) : 底層用來儲存資料的容器，一般來說它可以省略，但若後面有加第三參數，就必須把第二參數一併寫上 !greater<Node>(第三個參數) : 因為 C++ 預設priority_queue是由大到小，加入這行就會變成由大到小。- 這裡的
greater<Node>會比較 pair 的第一個參數，找到其中最小的，舉例 :- pq.push({5,1})
- pq.push({3,2})
- pq.push({7,3})
- pq.top() <— 會回傳 (3,2)
- 總結 : 可以把它想成「我要一個會自動排序的佇列,永遠把最小的放在前面」，如此一來就可以抓距離小的節點出來。
PS : node 的定義是 (距離 , 節點) ; pair 的定義是 (節點 , 距離)
priority_queue<元素型別, 底層容器, 比較方式> 變數名稱
class Graph {
private:
int V; // 節點數量
vector<vector<Edge>> adj; // 鄰接表
public:
Graph(int vertices) {
V = vertices;
adj.resize(V);
}
// 添加邊 (無向圖)
void addEdge(int u, int v, int weight) {
adj[u].push_back({v, weight});
adj[v].push_back({u, weight}); // 若為有向圖，移除此行
}
// Dijkstra 演算法
vector<int> dijkstra(int src) {
// 距離陣列，初始化為無限大，INF 在前面有定義過
vector<int> dist(V, INF);
// 記錄前一個節點（用於重建路徑），裡面的值全部填 -1
vector<int> parent(V, -1);
// 優先佇列 (最小堆)：(距離, 節點)
priority_queue<Node, vector<Node>, greater<Node>> pq;
...
}
}
第 4 步 #
dist[src] = 0: 將起點的距離設為 0pq.push({0,src}): 將 {0,src} push() 進priority_queue， 這步重要的地方在於，後面迴圈剛開始會先 pop() 一次，如果此時沒有 push() ， pop() 會有問題。while (!pq.empty()): 意思是只要priority_queue不是空的就要一直迴圈下去。if (d > dist[u]) continue;我看到這行的時候比較疑惑，後面會說明😀for (auto& edge : adj[u])這邊用迴圈進鄰接表看看節點u有哪些鄰居🏚，比如若u=A，而A鄰居有B和C，edge就會依序代表 ‘B’ 和 ‘C’- 接著是「鬆弛操作」，所謂鬆弛操作指的就是若
距離[當前節點] + 邊權重 < 距離[鄰居]則更新距離。對應到程式碼即 :u節點的距離 +u到v節點的權重有沒有 <v節點的距離 ?- 若有，則
v節點的距離更新為u節點 +u到v節點的權重 v節點的前驅節點更新為 ‘u’- 把 {
v的距離,v} 這樣的pair結構放到priority_queue中 - 然後就發生問題了😫
- 我們模擬一下其中一個可能的狀態 :
// 初始狀態
dist[2] = INF
// 第一次更新節點 2
dist[2] = 10
pq.push({10, 2}) // 加入 (距離=10, 節點=2)
// 後來又找到更短路徑
dist[2] = 5 // 更新為 5
pq.push({5, 2}) // 又加入 (距離=5, 節點=2)
// 現在優先佇列中有兩個節點 2:
// pq = [(5, 2), (10, 2), ...]
- 會發現，
priority_queue有兩筆「2 號節點」的資料，如過不進行處理會有大問題，此時我們就需要if (d > dist[u]) continue工作流程如下 :
// 第一次取出 (5, 2) - 距離最小的
int u = 2, d = 5;
if (5 > dist[2]) continue; // 5 > 5? 否 → 繼續處理 ✓
// 第二次取出 (10, 2) - 這是舊的資料
int u = 2, d = 10;
if (10 > dist[2]) continue; // 10 > 5? 是 → 跳過! ✓
- 最後在
return dist就行了 (注意 : Claude 沒有return parent如果有需要回追路徑，這部分需要處理，比如用參照的方式處理它)
還記的前面提到我們訪問到某一個點需要將該點標記為 “已訪問” 嗎 ?正常來說應該會用一個存放布林值的陣列紀錄，類似
if (visited[u]) continue;，但 Claude 這邊用if (d > dist[u]) continue;做到同樣的效果。
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <utility>
#include <functional>
// 定義無限大
const int INF = numeric_limits<int>::max();
// 邊的結構 (目標節點, 權重)
typedef pair<int, int> Edge;
// priority_queue 中的元素 (距離, 節點)
typedef pair<int, int> Node;
class Graph{
private:
int V; // 節點數量
vector<vector<Edge>> adj; // 鄰接表
public:
Graph(int vertices) {
V = vertices;
adj.resize(V);
}
// 添加邊 (無向圖)
void addEdge(int u, int v, int weight) {
adj[u].push_back({v, weight});
adj[v].push_back({u, weight}); // 若為有向圖，移除此行
}
// Dijkstra 演算法
vector<int> dijkstra(int src) {
// 距離陣列，初始化為無限大
vector<int> dist(V, INF);
// 記錄前一個節點（用於重建路徑）
vector<int> parent(V, -1);
// 優先佇列 (最小堆)：(距離, 節點)
priority_queue<Node, vector<Node>, greater<Node>> pq;
// 起始點距離為 0
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
// 取出距離最小的節點
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
// 如果這個距離已經不是最短的，跳過
if (d > dist[u]) continue;
// 檢查所有鄰居
for (auto& edge : adj[u]) {
int v = edge.first; // 鄰居節點
int weight = edge.second; // 邊的權重
// 鬆弛操作
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
return dist;
}
}
UVA-10986 #
這是 UVA-10986 按照上面方法所做的練習，有興趣可以看看，只是因為是寫程式競賽題目，基本沒甚麼可讀性
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include <functional>
using namespace std;
int main(){
const int INF = 9999999999;
typedef pair<int,int> Edge;
typedef pair<int,int> Node;
int N;
cin>>N;
int n,m,src,tar,cCnt = 0;
while(N--){
int u,v,wei;
cin>>n>>m>>src>>tar;
vector<vector<Edge>>Graph(n);
while(m--){
//input
cin>>u>>v>>wei;
Graph[u].push_back({v,wei});
Graph[v].push_back({u,wei});
}
//dijkstra
vector<int>dist(n,INF);
priority_queue<Node, vector<Node>, greater<Node>> pq;
dist[src] = 0;
pq.push({0,src});
while(!pq.empty()){
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
if(d > dist[u])continue;
for(auto& edge : Graph[u]){
int v = edge.first;
int weigt = edge.second;
if(dist[u]+weigt < dist[v]){
dist[v] = dist[u]+weigt;
pq.push({dist[v],v});
}
}
}
cout<<"Case #"<<++cCnt<<":"<<" ";
if(dist[tar]!= INF)cout<<dist[tar]<<endl;
else cout<<"unreachable"<<endl;
}
}
