上一篇已經跑過一次 Dijkstra，知道尋找最短路徑的過程中，需要記錄幾個重要資訊：

• Distance： 目前從起點到這個節點的最短距離
• Previous： 目前是從哪個節點走過來
• Visited： 這個節點是否已經處理完成
• Priority Queue： 接下來有哪些節點等待處理

今天就要試著把昨天 Graph 的流程，真的轉成 TypeScript。
不過開始之前還有一個問題：
圖形的 Graph，要怎麼變成程式可以使用的資料？

首先使用 Day 19 學過的 Adjacency List（相鄰串列） 表示 Graph：

const dijkstraData = {
  A: [{ B: 4 }, { C: 2 }, { D: 7 }],
  B: [{ A: 4 }, { C: 3 }, { E: 1 }, { F: 5 }],
  C: [{ A: 2 }, { B: 3 }, { D: 6 }, { F: 8 }],
  // ...
}

另外準備三個資料：

const table = []              // 記錄 Distance
const visited = new Set()     // 已經處理完成
let q = []                    // 等待處理

第一輪：把手算的 A 寫成程式

上一篇第一步是從 A 開始：

A → B = 4
A → C = 2
A → D = 7

所以程式要做的事情也很直接：

const firstNodeData = data[startNode]

for (const neighbor of firstNodeData) {
  // 取得 Neighbor
  // 更新 Distance
  // 放進 q
}

visited.add(startNode)

最後得到：

q：
B = 4
C = 2
D = 7

接著 Dijkstra 要選 Distance 最小的 Node，所以找到：

C = 2

對應程式：

const minDistance = Math.min(
  ...q.map((item) => item.distance)
)

const nextNode = q.find(
  (item) => item.distance === minDistance
)

到這裡其實都只是把昨天手算的步驟翻成程式。

第二輪：換 C，開始有點不一樣

現在從 C 繼續。

例如：

A → C = 2
C → F = 8

所以 F 的 Distance 不是 8，而是：

2 + 8 = 10

程式就變成：

const totalDistance =
  nextNode.distance + neighborDistance

再拿新的 Distance 跟原本的比較，新的比較短才更新。

這一輪我遇到兩個問題

• Neighbor 已經在 visited → 跳過，不要再走回去。
• Node 已經存在 q → 不要再 Push 一個，只更新比較短的 Distance。

寫到第三輪，我突然發現...等等流程重複了？

C 處理完後，下一個是 B。

於是我準備再寫一次：

找最小 Distance
→ 找 Neighbor
→ 計算 Distance
→ 更新 table
→ 更新 q
→ 加入 visited

但這不就是剛剛處理 C 做過的事情嗎？

如果下一個是 E，我又要再寫一次？

原來每一輪換的只有 Node，處理流程根本完全一樣。

所以我真正需要的不是一直複製 Code，而是：

while (q.length > 0) {
  // 找目前 Distance 最小的 Node
  // 處理它的 Neighbor
  // 更新 Distance
  // 處理完成後繼續下一輪
}

這樣就清楚多了。

結論

今天真的寫下去才發現，更重要的是把手算時重複出現的規則找出來：

找最小 Distance
↓
更新 Neighbor
↓
處理完成
↓
找下一個

只要 Queue 還有資料，就重複這件事。

所以最後才會自然變成 while。

目前這一版已經可以得到最短 Distance，但還有一個東西沒處理：

我知道 A 到 G 最短是多少，卻不知道到底是怎麼走到 G 的。

這就是下一篇要加入的 Previous。

完整程式碼

function dijkstra(
  data: DijkstraGraph,
  startNode: string,
  endNode: string
) {
  /** 記錄各節點目前的 Distance */
  const table: TableNode[] = []

  /** 記錄已經處理完成的節點 */
  const visited = new Set<string>()

  /** 記錄等待處理的節點 */
  let q: QueueNode[] = []

  // 初始化 Distance Table
  for (const node in data) {
    table.push({
      node,
      distance: node === startNode ? 0 : Infinity,
    })
  }

  /** 第一輪：從起點開始 */
  const firstNodeData = data[startNode]

  if (!firstNodeData) return table

  for (const neighbor of firstNodeData) {
    const neighborNode = Object.keys(neighbor)[0]
    const neighborDistance = Object.values(neighbor)[0]

    if (
      neighborNode === undefined ||
      neighborDistance === undefined
    ) {
      continue
    }

    const tableNode = table.find(
      (item) => item.node === neighborNode
    )

    if (
      tableNode &&
      tableNode.distance > neighborDistance
    ) {
      tableNode.distance = neighborDistance
    }

    q.push({
      node: neighborNode,
      distance: neighborDistance,
    })
  }

  // 起點處理完成
  visited.add(startNode)

  /** 接著重複處理 Queue */
  while (q.length > 0) {
    const distances = q.map((item) => item.distance)
    const minDistance = Math.min(...distances)

    const nextNode = q.find(
      (item) => item.distance === minDistance
    )

    if (!nextNode) break

    // Queue 中最小的已經是終點
    if (nextNode.node === endNode) {
      break
    }

    const nextNodeData = data[nextNode.node]

    if (!nextNodeData) break

    for (const neighbor of nextNodeData) {
      const neighborNode = Object.keys(neighbor)[0]
      const neighborDistance = Object.values(neighbor)[0]

      if (
        neighborNode === undefined ||
        neighborDistance === undefined
      ) {
        continue
      }

      // 已經處理完成的節點直接跳過
      if (visited.has(neighborNode)) {
        continue
      }

      const totalDistance =
        nextNode.distance + neighborDistance

      /** 更新 Distance Table */
      const tableNode = table.find(
        (item) => item.node === neighborNode
      )

      if (
        tableNode &&
        tableNode.distance > totalDistance
      ) {
        tableNode.distance = totalDistance
      }

      /** 更新 Queue */
      const existingNode = q.find(
        (item) => item.node === neighborNode
      )

      if (existingNode) {
        if (existingNode.distance > totalDistance) {
          existingNode.distance = totalDistance
        }
      } else {
        q.push({
          node: neighborNode,
          distance: totalDistance,
        })
      }
    }

    // nextNode 處理完成
    visited.add(nextNode.node)

    // 從等待處理的 Queue 移除
    q = q.filter(
      (item) => item.node !== nextNode.node
    )
  }

  return table
}

console.log(dijkstra(dijkstraData, "A", "G"))