112 年 國立中山大學資訊工程學系資訊安全碩士班《離散數學與演算法》

核心觀念

本題主要考驗離散數學中的重複組合（Combination with Repetition / Multiset）與計數原理。

1. 等價關係（Equivalence Relation）與多重集（Multiset）：
   題目定義：若一個 $n$ 位數整數可以透過另一個整數的數字重排（Rearrangement）而得到，則兩數視為等價（Equivalent）。
   這意味著：決定一個 $n$ 位數整數所在的「等價類（Equivalence Class）」，只需考慮該整數中各數字（$0, 1, 2, \dots, 9$）出現的次數，而不需考慮數字出現的順序。因此，「互不等價的 $n$ 位數整數個數」即等於「從 10 種數字 $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ 中，可重複地選出 $n$ 個數字所構成的不同多重集數量」。

2. 重複組合公式：
   從 $n$ 種不同的元素中，可重複地取 $r$ 個元素組合，其種類數記為 $H(n, r)$ 或 $H^n_r$，可轉換為普通組合數 $C$：
   $H(n, r) = C(n + r - 1, r) = C(n + r - 1, n - 1)$

3. 受限重複組合與分類討論（或生成函數法）：
   當部分元素有次數限制（例如出現至多一次）時，可利用**分類討論法（按限制元素的總選取次數分類）或生成函數（Generating Function）**求得指定次數的係數。

---

解題方法

(a) 小題推導：計算互不等價的 6 位數整數個數

• 問題轉化：
  位數 $n = 6$。可用的數字集合為 $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$，共 10 種數字。
  設數字 $i$ 出現的次數為 $x_i$（其中 $0 \le i \le 9$），由於數字可包含前導零，且不考慮順序，故求互不等價的 6 位數整數個數，等價於求下列方程式非負整數解的組數：
  $x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 6, \quad x_i \in \mathbb{N} \cup \{0\}$

• 步驟與計算：
  此為標準重複組合問題，從 10 種數字中可重複地選取 6 個數字：
  $H(10, 6) = C(10 + 6 - 1, 6) = C(15, 6)$
  利用組合數展開計算：
  $C(15, 6) = \frac{15 \times 14 \times 13 \times 12 \times 11 \times 10}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 5005$

(b) 小題推導：數字 3、5、7 至多出現一次時的個數

• 條件分析：
  數字集合分為兩類：

  1. 受限數字：$\{3, 5, 7\}$，共 3 種數字，出現次數 $x_3, x_5, x_7 \in \{0, 1\}$。
  2. 無限制數字：$\{0, 1, 2, 4, 6, 8, 9\}$，共 7 種數字，出現次數 $x_i \ge 0$。

  需滿足總位數：
  $\sum_{i=0}^9 x_i = 6$

• 解題步驟：按受限數字的總選取個數 $k$ 分類討論

  設從受限數字集合 $\{3, 5, 7\}$ 中選出的數字種類總數為 $k$（$k \in \{0, 1, 2, 3\}$）：

核心觀念

本題考查**指數型生成函數（Exponential Generating Function, EGF）**的定義及其級數求和。

1. 指數型生成函數（EGF）定義：
   對於數列 $\langle a_n \rangle = \langle a_0, a_1, a_2, \dots \rangle$，其指數型生成函數 $E(x)$ 定義為：
   $E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = a_0 + a_1 x + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \dots$

2. 無窮等比級數求和公式：
   當 $|x| < 1$ 時，公比為 $x$、首項為 $1$ 的無窮等比級數收斂至閉合形式（Closed Form）：
   $\sum_{n=0}^{\infty} x^n = 1 + x + x^2 + x^3 + \dots = \frac{1}{1-x}$

---

解題方法

步驟一：確定數列通項
題目給定的數列為 $0!, 1!, 2!, 3!, \dots$，其通項公式可寫為：
$a_n = n!, \quad \text{其中 } n \ge 0$

步驟二：代入指數型生成函數定義
將 $a_n = n!$ 代入 EGF 的定義式中：
$E(x) = \sum_{n=0}^{\infty} n! \cdot \frac{x^n}{n!}$

步驟三：約分化簡
由於對所有 $n \ge 0$，$n!$ 皆不為 $0$，分子與分母的 $n!$ 可以直接相消：

將箱子依大小排列為

$B_1<B_2<\cdots<B_{65}.$

物品小於最小箱子 $B_1$，故可放入 $B_1$；又因較大箱子可容納較小箱子，因此可逐層套裝：

核心觀念

1. 整除的同餘性質（Divisibility Properties）
   若 $a, b, n$ 皆為整數且 $n > 0$，根據整除的線性組合性質：
   $n \mid (a \cdot n + b) \iff n \mid b$
   因為對任意整數 $n$， $n \mid (a \cdot n)$ 恆成立。

2. 算術基本定理與因數個數公式（Fundamental Theorem of Arithmetic）
   任何大於 1 的正整數 $N$ 都可以唯一分解為質因數的乘積。若 $N$ 的質因數分解式為：
   $N = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$
   則 $N$ 的所有正因數個數 $d(N)$ 計算公式為：
   $d(N) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$

3. 質數判定試除法（Trial Division）
   欲檢驗自然數 $m$ 是否為質數，僅需測試不大於 $\sqrt{m}$ 的所有質數是否能整除 $m$。

---

解題方法

步驟一：簡化整除條件

題目要求找出能使 $n \mid (69373n + 342247)$ 成立的正整數 $n$ 個數。
將分子拆解為兩項：
$\frac{69373n + 342247}{n} = 69373 + \frac{342247}{n}$
由於 $69373$ 為整數，若要使上式結果為整數，當且僅當 $n$ 能整除 $342247$（即 $n \mid 342247$）。
因此，本題等價於求正整數 $342247$ 的正因數個數。

步驟二：對 $342247$ 進行質因數分解

1. 計算開平方根以確定試除上限：
   $\sqrt{342247} \approx 585.02$
2. 由小到大測試質因數：
   • 排除 $2, 3, 5$：尾數非偶數（非 2 的倍數）、數字和 $3+4+2+2+4+7=22$（非 3 的倍數）、尾數非 $0, 5$（非 5 的倍數）。
   • 測試 $7, 11, 13, 17$：均無法整除。
   • 測試質數 $19$：
     $342247 = 19 \times 18013$
     成功分解出質因數 $19$。

步驟三：檢驗商數 $18013$ 是否為質數

1. 計算開平方根上限：
   $\sqrt{18013} \approx 134.21$
2. 檢驗小於 $134.21$ 的所有質數：

核心觀念

本題考查**組合數學（Combinatorics）中的整數拆解（Integer Partition）與生成函數（Generating Function）**之建立。

1. 整數拆解（Partition）：將非負整數 $n$ 表示為若干個正整數之和（不考慮加數的順序），這些被相加的正整數稱為加數（Summands / Parts）。
2. 生成函數建立原則（Product Rule for Generating Functions）：
   對於每個可選的正整數加數 $k \in \{1, 2, 3, \dots\}$，若其出現次數（重數 multiplicity） $c_k$ 受限於某個集合 $S_k \subseteq \{0, 1, 2, \dots\}$，則加數 $k$ 所對應的生成函數因子為：
   $f_k(x) = \sum_{c_k \in S_k} x^{k \cdot c_k}$
   根據組合計數的乘法原理，整體整數拆解數的生成函數 $P(x)$ 即為所有加數因子的無窮乘積：
   $P(x) = \prod_{k=1}^{\infty} f_k(x)$
3. 無窮等比級數求和公式：
   當 $|r| < 1$ 時，首項為 $a$、公比為 $r$ 的無窮等比級數和為：
   $\sum_{m=0}^{\infty} a r^m = \frac{a}{1 - r}$

---

解題方法

步驟一：分析個別加數 $k$ 的出現次數條件

題目限制「每個加數若出現，其出現次數必須為奇數次」。
對於任一給定的正整數加數 $k$（$k = 1, 2, 3, \dots$）：

• 加數 $k$ 可以不出現（即出現 $0$ 次，貢獻次方 $k \cdot 0 = 0$）。
• 若加數 $k$ 出現，則其出現次數 $c_k$ 必須為奇數，即 $c_k \in \{1, 3, 5, 7, \dots\}$（貢獻次方 $k \cdot 1, k \cdot 3, k \cdot 5, \dots$）。

因此，加數 $k$ 的可能出現次數集合為 $S_k = \{0, 1, 3, 5, 7, \dots\}$。

步驟二：撰寫加數 $k$ 的生成函數因子

將加數 $k$ 對應的所有可能次方項相加，得到加數 $k$ 的生成函數因子 $f_k(x)$：
$f_k(x) = x^{0 \cdot k} + x^{1 \cdot k} + x^{3 \cdot k} + x^{5 \cdot k} + x^{7 \cdot k} + \dots$
$f_k(x) = 1 + x^k + x^{3k} + x^{5k} + x^{7k} + \dots$

步驟三：化簡單一因子 $f_k(x)$

觀察 $f_k(x)$ 中從第二項開始的無窮級數 $x^k + x^{3k} + x^{5k} + \dots$：
此級數為首項為 $x^k$、公比為 $x^{2k}$ 的無窮等比級數。利用等比級數求和公式可得：
$x^k + x^{3k} + x^{5k} + \dots = \frac{x^k}{1 - x^{2k}}$

因此，$f_k(x)$ 可化簡表示為：
$f_k(x) = 1 + \frac{x^k}{1 - x^{2k}} = \frac{1 - x^{2k} + x^k}{1 - x^{2k}} = \frac{1 + x^k - x^{2k}}{1 - x^{2k}}$

步驟四：組合成全體生成函數 $P(x)$

將所有正整數 $k \ge 1$ 的因子相乘，即可得非負整數 $n$ 拆解為「每個加數出現奇數次」的拆解數生成函數 $P(x)$：
$P(x) = \prod_{k=1}^{\infty} \left( 1 + x^k + x^{3k} + x^{5k} + \dots \right)$
$P(x) = \prod_{k=1}^{\infty} \left( 1 + \frac{x^k}{1 - x^{2k}} \right) = \prod_{k=1}^{\infty} \frac{1 + x^k - x^{2k}}{1 - x^{2k}}$

---

選項分析

本題為非選擇題（計算問答題）。為深化觀念，以下針對生成函數構造中各個代表項與常見錯誤型態進行結構解析與比對：

核心觀念

本題考查數論（Number Theory）中關於質數分佈的基本性質，核心知識點包含：

1. 質數（Prime number）的定義：大於 $1$ 的整數 $p$，若其正因數僅有 $1$ 與 $p$ 本身，則稱 $p$ 為質數。
2. 算術基本定理（Fundamental Theorem of Arithmetic）/ 質因數存在性：任何大於 $1$ 的整數要麼本身是質數，要麼可以唯一分解為有限個質數的乘積。因此，任意整數 $n > 1$ 必存在至少一個質因數。
3. 整數的可整除性（Divisibility）線性組合性質：若 $p$ 能整除 $a$ 且 $p$ 能整除 $b$（記作 $p \mid a$ 且 $p \mid b$），則 $p$ 必能整除兩者的線性組合 $ax + by$。特別地，$p \mid (a - b)$。
4. 反證法（Proof by Contradiction）：假設欲證命題的反面成立，經由邏輯推導得出與已知定理或事實矛盾的結果，從而證明原命題必定成立。

---

解題方法

採用歐幾里得（Euclid）經典的反證法進行嚴嚴謹推導：

1. 提出反證假設：
   假設質數的數量是有限的（Finitely many），設全體質數共有 $n$ 個，依從小到大的順序排列為：
   $p_1, p_2, p_3, \dots, p_n$
   其中 $p_1 = 2, p_2 = 3, p_3 = 5, \dots$。

2. 構造特殊整數：
   定義整數 $N$ 為所有已知質數的乘積再加上 $1$：
   $N = (p_1 \cdot p_2 \cdot p_3 \cdots p_n) + 1$

3. 分析 $N$ 的質因數：
   因為 $p_1 \ge 2$，所以 $N \ge 2 \cdot 3 + 1 = 7 > 1$。
   根據算術基本定理，整數 $N$ 必存在至少一個質因數，記此質因數為 $p$。

4. 推導邏輯矛盾：

   • 由於 $p_1, p_2, \dots, p_n$ 已經包含全體質數，質數 $p$ 必須是該列表中的某一個質數，即存在 $1 \le k \le n$ 使得 $p = p_k$。
   • 因為 $p$ 是 $p_1 \cdot p_2 \cdots p_n$ 的其中一個因數，故：
     $p \mid (p_1 \cdot p_2 \cdots p_n)$
   • 同時，由 $p$ 是 $N$ 的質因數可知：
     $p \mid N$

核心觀念

河內塔（Tower of Hanoi）問題為經典的**遞迴（Recursion）與分治法（Divide and Conquer）**應用範例。

1. 基本規則：
   • 共有三根柱子：來源柱（Source, $A$）、目標柱（Target, $C$）、輔助柱（Auxiliary, $B$）。
   • 來源柱上有 $n$ 個圓盤，由上至下依尺寸由小到大排列。
   • 每次僅能移動一個圓盤，且在移動過程中，較大圓盤絕對不可疊放在較小圓盤之上。
2. 分治策略：
   • 將「搬動 $n$ 個圓盤」的大問題，化簡為「搬動 $n-1$ 個圓盤」的相同結構子問題。
3. 複雜度分析基礎：
   • 建立遞迴關係式（Recurrence Relation），並運用**代入展開法（Substitution Method）**精確求解移動次數與時間複雜度。

---

解題方法

1. 遞迴演算法邏輯與步驟

若要將 $n$ 個圓盤從來源柱（$A$）借助輔助柱（$B$）搬移至目標柱（$C$）：

• Base Case（基本情況）：
  當 $n = 1$ 時，直接將該圓盤從 $A$ 搬移至 $C$。
• Recursive Step（遞迴步驟）：
  1. 步驟一：將最上方的 $n-1$ 個圓盤從 $A$ 移動至 $B$（此時 $C$ 為輔助柱）。
  2. 步驟二：將 $A$ 上剩餘的最大圓盤（第 $n$ 個）直接移動至 $C$。
  3. 步驟三：將暫存在 $B$ 的 $n-1$ 個圓盤從 $B$ 移動至 $C$（此時 $A$ 為輔助柱）。

2. 演算法虛擬碼（Pseudocode）

Algorithm Hanoi(n, Source, Target, Auxiliary):
    if n == 1:
        Move disk 1 from Source to Target
        return
    
    // 步驟一：將 n-1 個圓盤從 Source 移至 Auxiliary
    Hanoi(n - 1, Source, Auxiliary, Target)
    
    // 步驟二：將最大的第 n 個圓盤從 Source 移至 Target
    Move disk n from Source to Target
    
    // 步驟三：將 n-1 個圓盤從 Auxiliary 移至 Target
    Hanoi(n - 1, Auxiliary, Target, Source)

3. 詳細時間複雜度推導 (Time Complexity Analysis)

設 $T(n)$ 為移動 $n$ 個圓盤所需的總搬移次數（基本操作數）。

依據演算法的三大步驟，可建立遞迴關係式：
$T(n) = \begin{cases} 1, & \text{if } n = 1 \\ 2T(n-1) + 1, & \text{if } n > 1 \end{cases}$

利用**反覆代入法（Repeated Substitution Method）**展開：
$T(n) = 2T(n-1) + 1$
$= 2\big(2T(n-2) + 1\big) + 1 = 2^2 T(n-2) + 2 + 1$
$= 2^2 \big(2T(n-3) + 1\big) + 2 + 1 = 2^3 T(n-3) + 2^2 + 2 + 1$

導出第 $k$ 步展開的一般通式：
$T(n) = 2^k T(n-k) + \sum_{i=0}^{k-1} 2^i = 2^k T(n-k) + (2^k - 1)$

核心觀念

Merge Sort（合併排序法）是經典的 Divide-and-Conquer（分治法） 演算法。其核心思想是將一個複雜的大問題遞迴地分割為若干個規模較小、結構相同的子問題，待子問題各自求解完成後，再將子問題的解答合併以求得原問題的最終解答。

描述 Merge Sort 並詳細分析其時間複雜度，主要涵蓋以下關鍵定義與分析工具：

1. Divide-and-Conquer 三大階段：
   • Divide（分割）：將長度為 $n$ 的未排序陣列從中間切開，拆分為兩個長度約為 $n/2$ 的子陣列。
   • Conquer（克服/遞迴排序）：遞迴呼叫 MergeSort，分別對左半部與右半部的子陣列進行排序。
   • Combine（合併/Merge）：將兩個已經排序好的子陣列合併成一個整體排序完成的陣列。
2. 遞迴關係式（Recurrence Relation）：
   將演算法執行時間表示為子問題時間與合併時間的遞迴式：
   $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$
3. 複雜度分析工具：
   • 展開代換法（Substitution / Iterative Expansion Method）
   • 遞迴樹法（Recursion Tree Method）
   • 主定理（Master Theorem）

---

解題方法

1. Merge Sort 演算法描述與虛擬碼

Merge Sort 主要由兩個函數組成：主遞迴函數 MergeSort 與核心合併函數 Merge。

(1) MergeSort(A, low, high)

主函數負責界定陣列範圍，當範圍內元素多於 1 個時計算中點並發起遞迴呼叫，最後呼叫 Merge 進行合併。

MergeSort(A, low, high):
    if low < high:
        mid = low + (high - low) / 2    // 計算中間索引（避免溢位）
        MergeSort(A, low, mid)          // 遞迴排序左半部 A[low..mid]
        MergeSort(A, mid + 1, high)      // 遞迴排序右半部 A[mid+1..high]
        Merge(A, low, mid, high)        // 合併左右兩個已排序子陣列

(2) Merge(A, low, mid, high)

合併函數將兩個相鄰且已排序的子陣列 $A[low..mid]$ 與 $A[mid+1..high]$ 合併為單一排序陣列。利用雙指標（Two Pointers）分別指向兩子陣列開頭，比較元素大小後依序填入輔助陣列，最後複製回原陣列 $A$。

Merge(A, low, mid, high):
    n1 = mid - low + 1
    n2 = high - mid
    建立輔助陣列 L[0..n1-1] 與 R[0..n2-1]
    
    for i = 0 to n1-1:
        L[i] = A[low + i]
    for j = 0 to n2-1:
        R[j] = A[mid + 1 + j]
        
    i = 0, j = 0, k = low
    while i < n1 and j < n2:
        if L[i] <= R[j]:        // 條件包含等於 (<=) 以維持穩定度 (Stability)
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        k = k + 1
        
    while i < n1:               // 複製左半部剩餘元素
        A[k] = L[i]
        i = i + 1
        k = k + 1
        
    while j < n2:               // 複製右半部剩餘元素
        A[k] = R[j]
        j = j + 1
        k = k + 1

---

2. 時間複雜度詳細推導

第一步：建立遞迴關係式 (Recurrence Relation)

設 $T(n)$ 為處理長度為 $n$ 之陣列所需的總執行時間：

• Base Case：當 $n = 1$ 時，只需常數時間判斷邊界，故 $T(1) = \Theta(1)$。
• Recursive Case：當 $n > 1$ 時：
  • Divide：計算中點 $mid$ 需要常數時間 $O(1)$。
  • Conquer：遞迴排序兩個規模為 $n/2$ 的子陣列，共需花費 $2T(n/2)$ 時間。
  • Combine：Merge 函數需要雙指標掃描並搬移 $n$ 個元素，花費 $\Theta(n)$ 時間。

綜合上述，遞迴關係式完整定義如下：
$T(n) = \begin{cases} c_1, & n = 1 \\ 2T\left(\frac{n}{2}\right) + cn, & n > 1 \end{cases}$
其中 $c_1, c > 0$ 為常數。

---

第二步：推導時間複雜度（提供三種嚴密推導方式）

推導方式一：展開代換法（Substitution / Iterative Expansion Method）

將遞迴式連續展開：
$T(n) = 2T\left(\frac{n}{2}\right) + cn$
$T(n) = 2\left[2T\left(\frac{n}{4}\right) + c\left(\frac{n}{2}\right)\right] + cn = 4T\left(\frac{n}{4}\right) + 2cn$
$T(n) = 4\left[2T\left(\frac{n}{8}\right) + c\left(\frac{n}{4}\right)\right] + 2cn = 8T\left(\frac{n}{8}\right) + 3cn$

將其推廣至第 $k$ 次展開：
$T(n) = 2^k T\left(\frac{n}{2^k}\right) + k \cdot cn$

當遞迴到達基底條件，即 $\frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2 n$ 時代入：
$T(n) = n \cdot T(1) + (\log_2 n) \cdot cn$
$T(n) = c_1 n + c n \log_2 n$
$T(n) = \Theta(n \log n)$

---

推導方式二：遞迴樹法（Recursion Tree Method）

構建遞迴結構樹並計算各層總工作量：

核心觀念

1. 單源最短路徑問題（Single-Source Shortest Path, SSSP）：
   給定一個權重圖 $G = (V, E)$ 及源點 $s \in V$，目標為求出從 $s$ 到圖中所有頂點 $v \in V$ 的最短路徑權重之和。

2. 貪婪選擇性質（Greedy-Choice Property）與最佳子結構（Optimal Substructure）：
   Dijkstra 演算法採用貪婪策略。演算法維持一個已確定最短路徑的頂點集合 $S$，在每一步選擇當前距離估計值最小且尚未納入 $S$ 的頂點 $u$，將其納入集合 $S$ 中。其正確性依賴於「最短路徑的子路徑亦為最短路徑」之最佳子結構性質。

3. 鬆弛操作（Relaxation）：
   演算法更新頂點最短距離估計值的核心機制。對於任一條有向邊 $(u, v) \in E$，若經過頂點 $u$ 到達頂點 $v$ 的路徑距離比當前記錄的距離更短，則更新 $v$ 的距離估計值與前驅頂點：
   $\text{若 } d[u] + w(u, v) < d[v] \text{，則更新 } d[v] = d[u] + w(u, v) \text{ 且 } \pi[v] = u$

4. 非負權重限制（Non-negative Edge Weights）：
   Dijkstra 演算法的前提條件為所有邊的權重必須非負（即對所有 $(u, v) \in E$，均滿足 $w(u, v) \geq 0$）。若圖中含有負權邊，貪婪選擇機制將無法保證解的正確性。

---

解題方法

1. 演算法步驟描述

Dijkstra 演算法主要維護以下資料結構：

• $d[v]$：記錄從源點 $s$ 到頂點 $v$ 的當前最短距離估計值。
• $\pi[v]$：記錄最短路徑上頂點 $v$ 的前驅頂點（用於重建路徑）。
• $S$：存放已確定最短路徑的頂點集合。
• $Q$：以 $d[v]$ 為鍵值（Key）的最小優先佇列（Min-Priority Queue），包含所有 $V \setminus S$ 中的頂點。

詳細執行流程：

1. 初始化步驟：

   • 對所有頂點 $v \in V$，設定 $d[v] = \infty$、$\pi[v] = \text{NIL}$。
   • 將源點 $s$ 的距離設為 $d[s] = 0$。
   • 初始化集合 $S = \emptyset$。
   • 將圖中所有頂點加入優先佇列 $Q$。

2. 主迴圈執行：

   • 當優先佇列 $Q \neq \emptyset$ 時，重複執行以下操作：
     1. 從 $Q$ 中取出具有最小 $d[u]$ 值的頂點 $u$（EXTRACT-MIN(Q)）。
     2. 將頂點 $u$ 加入集合 $S$（$S = S \cup \{u\}$）。
     3. 針對頂點 $u$ 的每一個相鄰頂點 $v \in \text{Adj}[u]$ 進行鬆弛操作：
        若 $d[u] + w(u, v) < d[v]$，則將 $d[v]$ 更新為 $d[u] + w(u, v)$、將 $\pi[v]$ 設定為 $u$，並更新 $v$ 在優先佇列 $Q$ 中的位置（DECREASE-KEY(Q, v, d[v])）。

3. 演算法虛擬碼（Pseudo-code）：

DIJKSTRA(G, w, s)
1. INITIALIZE-SINGLE-SOURCE(G, s)
    for each vertex v in G.V
        d[v] = INF
        pi[v] = NIL
    d[s] = 0
2. S = empty_set
3. Q = G.V
4. while Q is not empty
5.     u = EXTRACT-MIN(Q)
6.     S = S union {u}
7.     for each vertex v in G.Adj[u]
8.         if d[v] > d[u] + w(u, v)
9.             d[v] = d[u] + w(u, v)
10.            pi[v] = u
11.            DECREASE-KEY(Q, v, d[v])

---

2. 時間複雜度詳細分析

設 $|V| = V$ 表示頂點個數，$|E| = E$ 表示邊的個數。

Dijkstra 演算法的總執行時間主要由優先佇列的三種操作決定：

• INITIALIZE-SINGLE-SOURCE：需要 $O(V)$ 時間。
• EXTRACT-MIN 操作：每個頂點恰好被取出一次，共執行 $V$ 次。
• DECREASE-KEY 操作：在最壞情況下，每一條邊都會觸發一次鬆弛更新，共執行 $E$ 次。

因此，整體時間複雜度可表示為通用公式：
$T(V, E) = O(V) + V \cdot T_{\text{EXTRACT-MIN}} + E \cdot T_{\text{DECREASE-KEY}}$

根據優先佇列的不同實現方式，時間複雜度分析如下：

1. 未排序陣列（Unordered Array）實作：

   • EXTRACT-MIN：需線性掃描長度為 $V$ 的陣列，花費 $O(V)$ 時間。
   • DECREASE-KEY：直接存取陣列位置修改數值，花費 $O(1)$ 時間。
   • 總時間複雜度：
     $T(V, E) = O(V) + V \cdot O(V) + E \cdot O(1) = O(V^2 + E) = \mathbf{O(V^2)}$
   • 適用情境：密集圖（Dense Graph），當 $E \approx V^2$ 時，陣列實作結構簡單且常數項小。

2. 二元堆積（Binary Heap）實作：

   • 建堆（Build-Heap）：花費 $O(V)$ 時間。