108 年 國立成功大學製造資訊與系統研究所丙組《程式設計》

本題考查堆疊 (Stack) 的基本操作 PUSH 與 POP。堆疊是一種後進先出 (LIFO) 的資料結構。操作會依序影響堆疊的頂端元素。

核心觀念：
堆疊 (Stack) 的 PUSH 操作將元素加入頂端，POP 操作則移除頂端元素並回傳。

解題過程：
我們將依序執行題目給定的操作，並記錄堆疊的狀態。堆疊 S 儲存在陣列 S[1..6]，S.top 指向堆疊頂端的索引。

1. 初始狀態： 堆疊 S 為空。
   S: [_, _, _, _, _, _], S.top = 0 (或視為未定義)

2. PUSH(S, 8)： 將 8 加入堆疊。
   S.top 增加 1，S[S.top] = 8。
   S: [8, _, _, _, _, _], S.top = 1

3. PUSH(S, 3)： 將 3 加入堆疊。
   S.top 增加 1，S[S.top] = 3。
   S: [8, 3, _, _, _, _], S.top = 2

4. PUSH(S, 4)： 將 4 加入堆疊。
   S.top 增加 1，S[S.top] = 4。
   S: [8, 3, 4, _, _, _], S.top = 3

5. POP(S)： 移除頂端元素。回傳 4。
   S.top 減少 1。
   S: [8, 3, _, _, _, _], S.top = 2

6. PUSH(S, 6)： 將 6 加入堆疊。
   S.top 增加 1，S[S.top] = 6。
   S: [8, 3, 6, _, _, _], S.top = 3

本題考查如何在一維陣列中實作兩個堆疊，並確保其空間利用效率最大化，即只有當陣列總空間被佔滿時才會發生堆疊溢位。

核心觀念：
傳統上，若將兩個堆疊分別放在陣列的起始和結尾，可以有效利用空間。一個堆疊從陣列的開始往後增長，另一個堆疊則從陣列的結尾往前增長。

解題過程：
假設我們有一個陣列 A 的大小為 n。我們將實作兩個堆疊，稱之為 stack1 和 stack2。

1. stack1 的實作：

   • stack1 將從陣列的起始位置 (索引 1) 開始增長。
   • 我們需要一個指標 top1 來記錄 stack1 的頂端位置。
   • 當 stack1 PUSH 一個元素時，top1 遞增，然後將元素存入 A[top1]。
   • 當 stack1 POP 一個元素時，先取得 A[top1] 的值，然後 top1 遞減。
   • 初始時，top1 可以設為 0 (表示空)。

2. stack2 的實作：

   • stack2 將從陣列的結尾位置 (索引 n) 開始往回增長。
   • 我們需要一個指標 top2 來記錄 stack2 的頂端位置。
   • 當 stack2 PUSH 一個元素時，top2 遞減，然後將元素存入 A[top2]。
   • 當 stack2 POP 一個元素時，先取得 A[top2] 的值，然後 top2 遞增。
   • 初始時，top2 可以設為 n + 1 (表示空，因為 top2 會先減 1 才存值)。

3. 堆疊溢位的判斷：

   • stack1 的 PUSH 操作只有在 top1 + 1 的位置仍然有效 (即 top1 + 1 < top2) 時才能進行。如果 top1 + 1 == top2，則表示 stack1 的頂端已經碰到 stack2 的底端，此時陣列空間已滿，發生溢位。
   • stack2 的 PUSH 操作只有在 top2 - 1 的位置仍然有效 (即 top2 - 1 > top1) 時才能進行。

本題考查循環佇列 (Circular Queue) 的基本操作 ENQUEUE (加入元素) 與 DEQUEUE (移除元素)。佇列是一種先進先出 (FIFO) 的資料結構。題目中使用一個固定大小的陣列 Q[1..6] 來實作佇列，並假設是循環佇列以處理滿載與空載的情況。

核心觀念：

• 佇列 (Queue)： 先進先出 (FIFO) 的資料結構。
• ENQUEUE： 將元素加入佇列的尾端。
• DEQUEUE： 從佇列的頭端移除元素。
• 循環佇列 (Circular Queue)： 使用固定大小的陣列實作佇列時，為了更有效率地利用空間，當隊列尾或頭到達陣列末端時，會繞回陣列的起始端。需要使用 front (或 head) 和 rear (或 tail) 指標，並配合模運算來處理循環。

解題過程：
我們將依序執行題目給定的操作，並記錄佇列的狀態。佇列 Q 儲存在陣列 Q[1..6]。我們假設使用 front 指向隊列頭元素的索引，rear 指向隊列尾元素的下一個可插入位置。
為了簡化，我們也可以假設 front 指向隊列頭元素，rear 指向隊列尾元素。這裡採用 front 指向頭，rear 指向尾的常見表示法，並用 size 變數來判斷隊列是否為空或滿。

方法一：使用 front, rear 及 size

• front: 隊列頭元素的索引。
• rear: 隊列尾元素的索引。
• size: 隊列中元素的數量。

初始狀態： 佇列 Q 為空。
Q: [_, _, _, _, _, _], front = 0, rear = -1, size = 0 (或 front = 1, rear = 0, size = 0，取決於定義，這裡假設 front=1, rear=0, size=0)

1. ENQUEU(Q, 4)： 加入 4。

   • rear 遞增並循環：rear = (rear + 1) % 6 = (0 + 1) % 6 = 1。
   • Q[rear] = 4。
   • size 遞增：size = 1。
   • Q: [_, 4, _, _, _, _], front = 1, rear = 1, size = 1

2. ENQUEU(Q, 1)： 加入 1。

   • rear 遞增並循環：rear = (rear + 1) % 6 = (1 + 1) % 6 = 2。
   • Q[rear] = 1。
   • size 遞增：size = 2。
   • Q: [_, 4, 1, _, _, _], front = 1, rear = 2, size = 2

3. ENQUEU(Q, 3)： 加入 3。

   • rear 遞增並循環：rear = (rear + 1) % 6 = (2 + 1) % 6 = 3。
   • Q[rear] = 3。
   • size 遞增：size = 3。
   • Q: [_, 4, 1, 3, _, _], front = 1, rear = 3, size = 3

4. DENQUEU(Q)： 移除頭元素。

   • 頭元素是 Q[front]，即 Q[1]，值為 4。
   • front 遞增並循環：front = (front + 1) % 6 = (1 + 1) % 6 = 2。
   • size 遞減：size = 2。
   • Q: [_, _, 1, 3, _, _], front = 2, rear = 3, size = 2 (元素 4 被移除)

5. ENQUEU(Q, 8)： 加入 8。

   • rear 遞增並循環：rear = (rear + 1) % 6 = (3 + 1) % 6 = 4。
   • Q[rear] = 8。
   • size 遞增：size = 3。
   • Q: [_, _, 1, 3, 8, _], front = 2, rear = 4, size = 3

6. DENQUEU(Q)： 移除頭元素。

   • 頭元素是 Q[front]，即 Q[2]，值為 1。
   • front 遞增並循環：front = (front + 1) % 6 = (2 + 1) % 6 = 3。
   • size 遞減：size = 2。
   • Q: [_, _, _, 3, 8, _], front = 3, rear = 4, size = 2 (元素 1 被移除)

最終狀態：
佇列 Q 包含元素 3, 8，頭元素是 3 (在 Q[3])，尾元素是 8 (在 Q[4])。

結果圖示：
(假設陣列索引是 1-based，front 指向頭元素，rear 指向尾元素，size 記錄元素個數)

• 初始：
  Q: [_, _, _, _, _, _], front = 1, rear = 0, size = 0

• ENQUEU(Q, 4)：
  Q: [_, 4, _, _, _, _], front = 1, rear = 1, size = 1

• ENQUEU(Q, 1)：
  Q: [_, 4, 1, _, _, _], front = 1, rear = 2, size = 2

• ENQUEU(Q, 3)：
  Q: [_, 4, 1, 3, _, _], front = 1, rear = 3, size = 3

• DENQUEU(Q)： (移除 4)
  Q: [_, _, 1, 3, _, _], front = 2, rear = 3, size = 2

本題考查如何使用單向鏈結串列 (Singly Linked List) 來實作佇列 (Queue)。

核心觀念：
佇列是一個先進先出 (FIFO) 的資料結構。

• ENQUEUE (加入元素)： 應在鏈結串列的尾端進行。
• DEQUEUE (移除元素)： 應在鏈結串列的頭端進行。
  單向鏈結串列的每個節點包含資料和指向下一個節點的指標。

實作細節：
為了高效地實作佇列，我們需要追蹤鏈結串列的頭 (front/head) 和尾 (rear/tail)。

1. 節點結構 (Node Structure)：
   每個節點包含一個資料欄位 (data) 和一個指向下一個節點的指標 (next)。

   struct Node {
       int data;
       Node* next;
   };
   

2. 佇列結構 (Queue Structure)：
   佇列結構需要兩個指標：

   • front: 指向鏈結串列的第一個節點 (隊列頭)。
   • rear: 指向鏈結串列的最後一個節點 (隊列尾)。
     當佇列為空時，front 和 rear 都為 NULL。

   class Queue {
   private:
       Node* front;
       Node* rear;
   public:
       Queue() : front(nullptr), rear(nullptr) {} // 建構子
       ~Queue(); // 解構子 (處理記憶體釋放)
   
       void enqueue(int data); // 加入元素
       int dequeue();         // 移除元素
       bool isEmpty();        // 檢查是否為空
       // (可選) peek() 取得頭元素但不移除
   };
   

3. ENQUEUE 操作 (加入元素)：

   • 建立一個新的節點，包含要加入的資料。
   • 如果佇列為空 (front == nullptr 或 rear == nullptr)：
     • 新節點同時是頭和尾，所以 front = new_node 且 rear = new_node。
   • 如果佇列不為空：
     • 將當前尾節點的 next 指標指向新節點 (rear->next = new_node)。
     • 更新尾指標為新節點 (rear = new_node)。

   void Queue::enqueue(int data) {
       Node* newNode = new Node();
       newNode->data = data;
       newNode->next = nullptr; // 新節點是尾端，其 next 指向 nullptr
   
       if (isEmpty()) {
           front = newNode;
           rear = newNode;
       } else {
           rear->next = newNode;
           rear = newNode;
       }
   }
   

本題要求根據給定的節點屬性（索引、鍵值、左子節點索引、右子節點索引）繪製一個二元樹。題目明確指出要繪製「以 index 6 為根節點」的樹。

核心觀念：

• 二元樹 (Binary Tree)： 一種樹形資料結構，其中每個節點最多有兩個子節點，通常稱為左子節點 (left child) 和右子節點 (right child)。
• 節點表示： 題目提供了一個表格，其中 index 是節點的唯一識別符，key 是節點的值，Left 是左子節點的 index，right 是右子節點的 index。NIL 表示沒有子節點。
• 根節點 (Root)： 樹的起始節點，在本次題目中是 index 6。

解題過程：
我們從 index 6 開始繪製，並根據 Left 和 right 欄位遞迴地構建樹。

1. 根節點： index 6。

   • Key: 18
   • Left child index: 1
   • Right child index: 4

         18 (6)
        /  \
       ?    ?
   

2. 處理左子節點 (index 1)：

   • Index: 1
   • Key: 12
   • Left child index: 7
   • Right child index: 3

         18 (6)
        /  \
      12(1)  ?
     /  \
    ?    ?
   

3. 處理右子節點 (index 4)：

   • Index: 4
   • Key: 10
   • Left child index: 5
   • Right child index: 9

         18 (6)
        /  \
      12(1) 10(4)
     /  \  /  \
    ?    ? ?    ?
   

4. 繼續處理左子節點的子節點 (index 7)：

   • Index: 7
   • Key: 7
   • Left child index: NIL
   • Right child index: NIL
   • 節點 7 是葉節點。

         18 (6)
        /  \
      12(1) 10(4)
     /  \  /  \
    7(7) ?  ?    ?
   

核心觀念

本題旨在測驗二元樹走訪（Binary Tree Traversal）的遞迴（Recursive）實作以及其時間複雜度分析（Time Complexity Analysis）。

• 樹的走訪定義：依照特定順序恰好拜訪樹中所有節點一次。二元樹最經典的深度優先走訪（Depth-First Search, DFS）包含前序（Pre-order）、中序（In-order）與後序（Post-order）。題目並未限定走訪順序，只要能保證每個節點的 key 都被印出且時間複雜度為 $O(n)$，三種走訪方式皆屬標準正確解答。
• 複雜度要求：若樹有 $n$ 個節點，遞迴函式對每個節點必須僅花費常數時間 $O(1)$ 的操作（印出 key 及呼叫子節點），總執行時間即為 $O(n)$。

---

解題方法

1. 切入點與演算法設計

採用中序走訪（In-order Traversal）（或前序/後序）的遞迴邏輯：

1. 終止條件（Base Case）：若當前節點為空指標（root == NULL），直接返回。
2. 遞迴步驟（Recursive Step）：
   • 遞迴拜訪左子樹：printTree(root->left)
   • 印出當前節點的 key：printf("%d ", root->key)（常數時間操作）
   • 遞迴拜訪右子樹：printTree(root->right)

2. 資料結構定義與程式碼（以 C 語言為例）

#include <stdio.h>

/* 定義二元樹節點結構 */
struct TreeNode {
    int key;
    struct TreeNode *left;
    struct TreeNode *right;
};

/* O(n) 遞迴程序：走訪並印出二元樹每個節點的 key */
void printTree(struct TreeNode *root) {
    if (root == NULL) {
        return; // Base case: 空節點直接返回
    }
    
    // 依序走訪：左子樹 -> 當前節點 -> 右子樹 (In-order)
    printTree(root->left);
    printf("%d ", root->key);
    printTree(root->right);
}

虛擬碼（Pseudocode）表示法（符合 CLRS 經典風格）：

PRINT-TREE(x)
1  if x ≠ NIL

本題考查廣度優先搜尋 (Breadth-First Search, BFS) 的演算法。BFS 使用佇列來探索圖，從一個起始節點開始，一層一層地向外擴展。

核心觀念：

• 廣度優先搜尋 (BFS)： 一種圖遍歷演算法，從起始節點開始，先訪問所有距離為 1 的鄰居，然後是距離為 2 的鄰居，依此類推。
• 佇列 (Queue)： BFS 的核心資料結構，用於儲存待訪問的節點。
• 已訪問標記 (Visited Set)： 用於記錄哪些節點已經被訪問過，避免重複訪問和無限循環。
• BFS 樹 (BFS Tree)： 當 BFS 遍歷一個連通圖時，可以構造出一棵 BFS 樹。樹的邊是從父節點指向子節點，其中父節點是先於子節點被訪問的節點，且子節點是該父節點的鄰居中第一個被發現的。

圖形分析 (Figure 1)：
Figure 1 是一個無向圖，節點有 A, B, C, D, E, F, G, H, I。
我們需要選擇一個起始節點來開始 BFS。題目沒有指定，通常選擇圖中的第一個節點或按字母順序第一個出現的節點。假設我們從節點 A 開始。

解題過程 (Part 1)：使用佇列展示 BFS 操作

我們使用一個佇列 Q 來儲存待訪問的節點，以及一個集合 visited 來記錄已訪問的節點。

初始狀態：

• Q = [] (空佇列)
• visited = {} (空集合)
• 選擇起始節點：A

1. 訪問節點 A：

   • 將 A 加入 Q。 Q = [A]
   • 將 A 加入 visited。 visited = {A}

2. 處理佇列中的節點：

   • DEQUEUE A： Q = []。

   • 印出 A (作為 BFS 樹的根)。

   • 訪問 A 的鄰居： B, C, E。

     • B：未訪問。加入 Q，visited。 Q = [B], visited = {A, B}
     • C：未訪問。加入 Q，visited。 Q = [B, C], visited = {A, B, C}
     • E：未訪問。加入 Q，visited。 Q = [B, C, E], visited = {A, B, C, E}

   • DEQUEUE B： Q = [C, E]。

   • 印出 B。

   • 訪問 B 的鄰居： A, C, E。

     • A：已訪問。忽略。
     • C：已訪問。忽略。
     • E：已訪問。忽略。
     • (注意：在無向圖中，邊是雙向的。B 的鄰居是 A, C, E。但因為 A, C, E 都已經在 visited 中，所以 B 的加入動作不會改變 Q 或 visited。)

   • DEQUEUE C： Q = [E]。

   • 印出 C。

   • 訪問 C 的鄰居： A, B, E, F, I。

     • A：已訪問。忽略。
     • B：已訪問。忽略。
     • E：已訪問。忽略。
     • F：未訪問。加入 Q，visited。 Q = [E, F], visited = {A, B, C, E, F}
     • I：未訪問。加入 Q，visited。 Q = [E, F, I], visited = {A, B, C, E, F, I}

   • DEQUEUE E： Q = [F, I]。

   • 印出 E。

   • 訪問 E 的鄰居： A, B, C, D, F。

     • A：已訪問。忽略。
     • B：已訪問。忽略。
     • C：已訪問。忽略。
     • D：未訪問。加入 Q，visited。 Q = [F, I, D], visited = {A, B, C, E, F, I, D}
     • F：已訪問。忽略。

   • DEQUEUE F： Q = [I, D]。

   • 印出 F。

   • 訪問 F 的鄰居： C, E, G, I。

     • C：已訪問。忽略。
     • E：已訪問。忽略。
     • G：未訪問。加入 Q，visited。 Q = [I, D, G], visited = {A, B, C, E, F, I, D, G}
     • I：已訪問。忽略。

   • DEQUEUE I： Q = [D, G]。

   • 印出 I。

   • 訪問 I 的鄰居： C, F。

     • C：已訪問。忽略。
     • F：已訪問。忽略。

   • DEQUEUE D： Q = [G]。

   • 印出 D。

   • 訪問 D 的鄰居： E, G, H。

     • E：已訪問。忽略。
     • G：已訪問。忽略。
     • H：未訪問。加入 Q，visited。 Q = [G, H], visited = {A, B, C, E, F, I, D, G, H}

   • DEQUEUE G： Q = [H]。

   • 印出 G。

   • 訪問 G 的鄰居： E, F, H, I。

     • E：已訪問。忽略。
     • F：已訪問。忽略。
     • H：已訪問。忽略。
     • I：已訪問。忽略。

本題考查深度優先搜尋 (Depth-First Search, DFS) 的演算法，以及如何從 DFS 遍歷結果繪製 DFS 樹。

核心觀念：

• 深度優先搜尋 (DFS)： 一種圖遍歷演算法，它盡可能深地探索圖的每一個分支，直到到達葉節點或死胡同，然後回溯。
• 遞迴 (Recursion) 或堆疊 (Stack)： DFS 通常使用遞迴或一個堆疊來實現。遞迴是 DFS 的自然表達方式。
• 已訪問標記 (Visited Set)： 用於記錄哪些節點已經被訪問過，避免重複訪問和無限循環。
• DFS 樹 (DFS Tree)： 當 DFS 遍歷一個圖時，可以構造出一棵 DFS 樹。樹的邊是從父節點指向子節點，其中父節點是先於子節點被訪問的節點，且子節點是父節點的一個未訪問過的鄰居。DFS 樹可以幫助我們理解圖的連通分量、是否有環等。

圖形分析 (Figure 2)：
Figure 2 是一個有向圖 (directed graph)。節點有 A, B, C, D, E, F, G, H。
同樣，題目沒有指定起始節點，我們假設從節點 A 開始。

解題過程 (Part 1)：展示 DFS 操作

DFS 通常是透過遞迴函數來實現。我們使用一個集合 visited 來記錄已訪問的節點。

初始狀態：

• visited = {} (空集合)
• 選擇起始節點：A

DFS 遞迴函數 (假設 dfs(node))：

1. 標記 node 為已訪問。
2. 對 node 進行處理 (例如，印出節點)。
3. 對於 node 的每一個鄰居 neighbor：
   • 如果 neighbor 未被訪問，則遞迴調用 dfs(neighbor)。

DFS 操作步驟 (從 A 開始)：

1. dfs(A)：
   • visited = {A}
   • 印出 A。
   • A 的鄰居：B, C。
     • dfs(B)：
       • visited = {A, B}
       • 印出 B。
       • B 的鄰居：D, E。
         • dfs(D)：
           • visited = {A, B, D}
           • 印出 D。
           • D 的鄰居：E。
             • dfs(E)：
               • visited = {A, B, D, E}
               • 印出 E。
               • E 沒有未訪問的鄰居 (F 已訪問)。
               • 返回。
           • D 的其他鄰居：(無)。
           • 返回。
         • B 的下一個鄰居 E：已訪問。忽略。
       • 返回。
     • A 的下一個鄰居 C：
     • dfs(C)：
       • visited = {A, B, D, E, C}
       • 印出 C。
       • C 的鄰居：F。
         • dfs(F)：
           • visited = {A, B, D, E, C, F}

核心觀念

本題考查帶權有向圖的單源最短路徑與最短路徑樹。對每個可從 $s$ 到達的頂點 $v$，記錄：

$$d(v)=\text{從 }s\text{ 到 }v\text{ 的最小路徑權重}$$

最短路徑樹中的父節點 $\pi(v)$ 必須滿足：

$$d(v)=d(\pi(v))+w(\pi(v),v)$$

圖中邊權皆為非負值，因此使用 Dijkstra 演算法。須特別依箭頭方向判讀：圖中 $t$ 與 $x$ 之間的邊為 $x\to t$，而 $u\to z$ 並不是通往 $u$ 的路徑。

解題方法

依序進行最短距離更新：

1. 從 $s$ 出發：

   $$d(t)=1,\qquad d(x)=10,\qquad d(w)=10$$

2. 取出距離最小的 $t$，經由 $t\to v$：

   $$d(v)=d(t)+1=2$$

3. 取出 $v$，更新 $y$ 與 $z$：

   $$d(y)=d(v)+10=12$$ $$d(z)=d(v)+1=3$$

4. $x$ 與 $w$ 的距離皆為 $10$：

   • 經由 $x\to y$ 可得 $10+10=20$
   • 經由 $w\to y$ 可得 $10+10=20$

   均不如目前的 $d(y)=12$。

5. 經由 $y\to z$ 的距離為 $12+1=13$，不如目前的 $d(z)=3$。頂點 $u$ 沒有從 $s$ 可達的入邊，因此 $d(u)=\infty$。

本題要求根據 Figure 4 中的圖例，說明 Dijkstra 演算法的工作流程。Figure 4 提供了兩個圖 (a) 和 (b)，展示了演算法在不同階段的狀態。

核心觀念：
Dijkstra 演算法用於尋找帶權重的圖中，從單一源節點到所有其他節點的最短路徑。它是一種貪婪演算法。
其關鍵步驟包括：

1. 初始化： 設定源節點的距離為 0，其他節點距離為無窮大。維護一個已訪問節點集合 (S) 和一個待處理節點集合 (Q，通常用優先級佇列實現)。
2. 迭代： 重複以下步驟直到 Q 為空：
   • 從 Q 中選取距離值最小的節點 u。
   • 將 u 加入 S。
   • 對於 u 的每個未訪問鄰居 v，計算通過 u 到達 v 的距離 (dist[u] + weight(u, v))。如果這個距離比當前記錄的 dist[v] 小，則更新 dist[v] 並記錄 u 為 v 的前驅節點。

圖形分析 (Figure 4)：
Figure 4 展示了 Dijkstra 演算法從源節點 s 開始的過程。

• 圖 (a) 可能代表演算法的初始狀態或某個中間狀態。
• 圖 (b) 則展示了演算法在執行過程中，更新了節點的距離和前驅節點。

解題步驟：
我們將模擬 Dijkstra 演算法，並對照 Figure 4 中的圖 (a) 和 (b) 來解釋其工作原理。
假設圖 (a) 是初始狀態，圖 (b) 是某個中間狀態。

節點與邊：

• 節點：s, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10 (這裡的數字節點表示方式比較特別，我們將按照圖中標示來理解)
• 邊與權重 (從圖 (a) 觀察)：
  • s → 0 (權重 5)
  • s → 1 (權重 10)
  • 0 → 2 (權重 2)
  • 0 → 3 (權重 9)
  • 0 → 4 (權重 6)
  • 2 → 5 (權重 2)
  • 3 → 6 (權重 7)
  • 4 → 7 (權重 8)
  • 5 → 8 (權重 3)
  • 6 → 9 (權重 4)
  • 7 → 10 (權重 5)

演算法模擬與 Figure 4 對照：

初始狀態 (對應 Figure 4 (a) 的部分信息)：

• 源節點：s
• dist[s] = 0
• dist[v] = infinity 對於所有其他節點 v。
• pred[v] = NIL 對於所有節點 v。
• visited = {}
• PQ (優先級佇列，包含節點及其當前距離)：{ s(0) }

步驟 1：

• 從 PQ 中提取 s(0)。visited = {s}。
• s 的鄰居是 0 和 1。
  • 更新 dist[0] = dist[s] + w(s, 0) = 0 + 5 = 5。pred[0] = s。
  • 更新 dist[1] = dist[s] + w(s, 1) = 0 + 10 = 10。pred[1] = s。
• PQ 變為 { 0(5), 1(10) }。
• (此時，Figure 4 (a) 顯示了節點 s 的距離為 0，節點 1 的距離為 10。節點 0 的距離尚未標示，但根據演算法，它應該是 5。)

步驟 2：

• 從 PQ 中提取 0(5)。visited = {s, 0}。
• 0 的鄰居是 2, 3, 4。
  • 更新 dist[2] = dist[0] + w(0, 2) = 5 + 2 = 7。pred[2] = 0。
  • 更新 dist[3] = dist[0] + w(0, 3) = 5 + 9 = 14。pred[3] = 0。
  • 更新 dist[4] = dist[0] + w(0, 4) = 5 + 6 = 11。pred[4] = 0。
• PQ 變為 { 1(10), 2(7), 3(14), 4(11) }。
• (Figure 4 (a) 顯示節點 2 的距離為 7，節點 3 的距離為 14，節點 4 的距離為 11。這與我們的計算一致。)

步驟 3：

• 從 PQ 中提取 1(10)。visited = {s, 0, 1}。
• 1 沒有標示的鄰居。
• PQ 變為 { 2(7), 3(14), 4(11) }。

步驟 4：

• 從 PQ 中提取 2(7)。visited = {s, 0, 1, 2}。
• 2 的鄰居是 5。
  • 更新 dist[5] = dist[2] + w(2, 5) = 7 + 2 = 9。pred[5] = 2。
• PQ 變為 { 3(14), 4(11), 5(9) }。
• (Figure 4 (b) 顯示節點 5 的距離為 9，前驅節點是 2。這與我們的計算一致，並且 Figure 4 (b) 標示了節點 2 的前驅節點為 0，這在步驟 2 中已經確定。)

步驟 5：

• 從 PQ 中提取 5(9)。visited = {s, 0, 1, 2, 5}。
• 5 的鄰居是 8。
  • 更新 dist[8] = dist[5] + w(5, 8) = 9 + 3 = 12。pred[8] = 5。
• PQ 變為 { 3(14), 4(11), 8(12) }。