上一篇已經把 Graph 畫面整理好了，今天終於要開始把前面寫好的 Dijkstra 執行過程做成動畫。

一開始我想得很單純，既然之前 Bubble Sort、Quick Sort 都是透過「快照」記錄每個時間點的狀態，那 Dijkstra 應該也是一樣。

所以原本預計記錄：

• 現在處理哪個 Node
• 正在檢查哪個 Neighbor
• 哪些 Node 等待處理
• 哪些 Node 已經確認

但真正做到最後的 Shortest Path Highlight 時，我卻沒想到還需要紀錄 Node 和 Edge。

明明前面已經算出整個最短路徑（Route），為什麼畫動畫時還需要另外整理 Node 和 Edge？

Route 不是已經有答案了嗎？

前面完成 Dijkstra 時，最後已經可以得到類似這樣的結果：

['A', 'B', 'E', 'F', 'G']

這已經告訴我從 A 到 G 的最短路徑會經過哪些 Node。

所以一開始我不太理解，為什麼做動畫時還要另外處理：

const pathNodes = new Set(path)
const pathEdges = new Set<string>()

後來才發現，Route 是演算法需要的結果，但畫面需要更明確的「顯示狀態」。

例如畫面要把最短路徑標成另一個顏色，就需要回答：

現在畫到 A，A 要不要亮？

現在畫到 A-B 這條線，它要不要亮？

所以我才另外整理成：

• pathNodes：判斷哪些 Node 屬於最短路徑
• pathEdges：判斷哪些 Edge 屬於最短路徑

為什麼 Node 還要另外整理？

原本的 Route 是 Array，所以我先把它轉成 Set：

const pathNodes = new Set(path)

這樣在處理每一個 Node 時，就可以直接確認它目前應該顯示什麼狀態：

for (const id in data) {
  if (pathNodes.has(id)) nodeStates[id] = 'path'
  else if (id === current) nodeStates[id] = 'current'
  else if (visited.has(id)) nodeStates[id] = 'visited'
  else if (queue.has(id)) nodeStates[id] = 'queued'
  else nodeStates[id] = 'default'
}

這個迴圈其實就是：

把 Graph 上的 Node 全部走一次，決定每個 Node 現在應該長什麼樣子。

除了最短路徑，還會一起判斷它現在是正在處理、已確認、等待處理，還是一般狀態。

只有 Node 還不夠，Edge 也要知道

接著我又遇到另一個問題。

假設 Route 是：

['A', 'B', 'E', 'F', 'G']

我知道這五個 Node 要亮起來，但畫面上的線也要跟著 Highlight。

所以還需要把 Route 中前後相鄰的 Node 組合成 Edge：

const pathEdges = new Set<string>()

for (let i = 1; i < path.length; i++) {
  pathEdges.add(
    edgeKey(path[i - 1]!, path[i]!)
  )
}

最後會得到類似：

A-B
B-E
E-F
F-G

有了這些資料後，畫面在處理每一條 Edge 時，就可以判斷：

for (const { from, to } of edges) {
  const key = edgeKey(from, to)

  if (pathEdges.has(key)) edgeStates[key] = 'path'
  else if (key === checkingKey) edgeStates[key] = 'checking'
  else edgeStates[key] = 'default'
}

所以這兩個迴圈其實做的是兩件很單純的事情：

第一個迴圈決定每個 Node 的狀態，第二個迴圈決定每條 Edge 的狀態。

這一刻，每個 Node 和 Edge 應該顯示成什麼樣子 ?

做到這裡，我才發現自己一開始對快照只有基本的結構，UI 所需要的還需要建立。

原本我以為只要記錄：

• 目前 Node
• 正在檢查的 Neighbor
• Visited
• Queue
• Route

就可以直接拿去播放動畫。

但實際上，還需要把這些資料再整理成畫面可以直接使用的狀態：

nodeStates
checkingNode
edgeStates
visitedCount

也就是說，每產生一張快照時，不只是把「這一刻發生什麼」存下來，還要先整理好：

這一刻，每個 Node 和 Edge 應該顯示成什麼樣子。

這樣 Vue 播放每一張快照時，就只需要根據狀態改變畫面，不需要再重新判斷一次 Dijkstra 的邏輯。

做到這裡，搜尋過程中的 Current、Checking、Queue、Visited，以及最後的 Shortest Path，終於都可以一步一步呈現在 Graph 上了。

完整實作紀錄

想看這一版完整的程式碼，可以直接查看：

查看完整實作紀錄