計算機網路上的 Dijkstra’s Algorithm 求最短路徑

紀錄 2026/05/20 計算機網路課程。

何謂 Dijkstra’s Algortihm？

Dijkstra’s algorithm 是一種用來解決「單一起點最短路徑」的演算法，也就是從某個起點出發，找出到圖中其他所有節點的最短距離，適用於邊權重非負數的加權圖，例如道路距離、網路傳輸成本、地圖導航等情境。

Dijkstra’s Algorithm 的演算主要思路為每次都選擇目前距離起點最近、且尚未確定最短距離的節點，然後用這個節點去更新它鄰居的距離。

Dijkstra’s algorithm 會維護兩個資訊（以寫程式上來說）：

項目	說明
`dist[]`	從起點到每個節點目前已知的最短距離
`visited[]`	該節點的最短距離是否已經確定

一開始起點距離設為 $0$，其他節點距離設為無限大 $∞$，之後演算法會不斷挑選目前 dist 最小的未拜訪節點，並更新它相鄰節點的距離，這個更新動作稱為 Relaxation，鬆弛操作。

若用普通陣列尋找最小距離節點，時間複雜度通常是 $O(V^2)$ ， $V$ 表示節點或稱頂點 Vertices。

若使用 priority queue，這樣的實作可改善成 $O((V+E)\log{V})$ ，$E$ 表示邊數。

Given an undirected weight graph following, find the shortest path and cost from point A to point F.

dijkstra

Solution:

d(B) stand for “distance of vertex B”.

P(B) stand for “Predecessor of vertex B”. Predecessor refers to the vertex before vertex B, A.

Set	$d(B), P(B)$	$d©, P©$	$d(D), P(D)$	$d(E), P(E)$	$d(F), P(F)$
${A}$	$4, A$	$\infty$	$7, A$	$3, A$ (Visit E)	$\infty$
${A, E}$	$4, A$ (Visit B)	$9, E$	$4, E$	(Already Visited)	$6, E$
${A, B, E}$	(Already Visited)	$6, B$	$4, E$ (Visit D)	(Already Visited)	$6, E$
${A, B, D, E}$	(Already Visited)	$6, B$ (Visit C)	(Already Visited)	(Already Visited)	$6, E$
${A, B, C, D, E}$	(Already Visited)	(Already Visited)	(Already Visited)	(Already Visited)	$6, E$ (Visit F)

From the table above, the shortest path and cost are as follows: $P^*_{A-F} = A-E-F, \text{cost} = 6$

由於 A 作為起點，因此先放進 Set 集合當中，接著就進到第一個 Round。第一個 Round 當中，判斷從 A 走到 B 的距離（尋找所有鄰居節點），是 4，因此 $d(B) = 4$，且走到 $B$ 節點的前一個節點為 $A$，因此 $P(B) = A$ ，以此類推。

由於從 A 走起無法直接走到 C（A 跟 C 不是鄰居），所以 $d©, P© = \infty$，先暫時設定無限。

第一回合走完後，尋找當中的最低 cost，發現是 $d(E), P(E) = 3, A$ ，因此選他進入集合，目前暫且走到 E 這一個節點。

接著從 E 開始作為第二回合，一樣尋找他的鄰居節點，需注意的是此時 cost 已經累積到 3 了，因為從 A 走到 E 要花 3 cost，之後若走到其他節點，例如 E 走到 C 並不是 $d©, P© = 6, E$，而是 $d©, P© = 3 + 6, E = 9, E$ 。

將整個表格都算完以後，最後從 F 的 $d(F), P(F) = 6, E$ 開始，往 $d(E), P(E)$、$d(D), P(D)$ 的方向開始做回溯，每次回溯都要記錄其 Predecessor 的節點，直到遇到有 $3, A$ 的為止。

這題記錄完後會長成 $F-E-A$ ，但你要反過來寫，因為 A 是起點，所以最後答案是 $P^*_{A-F}=A-E-F$ 。

最小 cost 的話直接看 $d(F), P(F) = 6, E$ ，當中 $d(F) = 6$ 就是最小 cost。

Given an undirected weight graph following, find the shortest path and cost from point A to point F.

dijkstra2

Set	$d(B), P(B)$	$d©, P©$	$d(D), P(D)$	$d(E), P(E)$	$d(F), P(F)$
${A}$	$2, A$	$5, A$	$1, A$ (Visit D)	$\infty$	$\infty$
${A, D}$	$2, A$ (Visit B)	$4, D$	(Already Visited)	$2, D$	$\infty$
${A, B, D}$	(Already Visited)	$4, D$	(Already Visited)	$2, D$ (Visit E)	$\infty$
${A, B, D, E}$	(Already Visited)	$3, E$ (Visit C)	(Already Visited)	(Already Visited)	$4, E$
${A, B, C, D, E}$	(Already Visited)	(Already Visited)	(Already Visited)	(Already Visited)	$4, E$ (Visit F)