上一篇已經把 Dijkstra 從手算轉成 TypeScript，可以算出每個 Node 從起點出發的最短 Distance。

但今天重新看結果時，我發現還少了一個很重要的資訊。

假設最後得到：

G = 10

我只知道「從 A 到 G 最短距離是 10」，卻不知道實際上是怎麼走到 G。

所以今天要補上昨天還沒處理的 Previous，把真正經過的 Path 找回來。

Previous 要記在哪裡？

一開始我原本想把 Previous 放進 visited，但重新整理後：

• visited：哪些 Node 已經處理完成
• q：哪些 Node 等待處理
• table：每個 Node 目前找到的最短 Distance

Previous 比較像是 Node 的路徑資訊，而且會跟著 Distance 一起改變。

例如第一次找到 F：

F
Distance = 10
Previous = C

後來找到更短的路：

F
Distance = 9
Previous = B

所以我直接把 Previous 加進 table：

type TableNode = {
  node: string
  distance: number
  previous: string
}

初始化時先設成空字串：

table.push({
  node,
  distance: node === startNode ? 0 : Infinity,
  previous: '',
})

Distance 更新時，Previous 也要一起更新

原本找到更短路徑時，只會更新 Distance：

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

但既然路徑變短了，「我是從誰走過來的」也要一起更新：

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

最後 table 就會像：

A  0   ""
B  4   A
C  2   A
D  7   A
E  5   B
F  7   E
G  10  F

這時不只知道 G 的 Distance 是 10，也可以透過 Previous 把路徑找回來。

從終點一路往回找

從 G 開始查看 Previous：

G.previous = F
F.previous = E
E.previous = B
B.previous = A

得到：

G → F → E → B → A

每一輪其實都在做一樣的事情：

記錄目前 Node
↓
如果已經回到起點就停止
↓
找到目前 Node 的 Previous
↓
繼續處理 Previous

所以這裡我用前面學過的 Recursion：

const routesNode: string[] = []

function routes(node: string): void {
  if (!node) return

  routesNode.push(node)

  if (node === startNode) return

  const currentNode = table.find(
    (item) => item.node === node
  )

  routes(currentNode?.previous ?? '')
}

每一輪都遵守同一個規則。

最後把 Path 反過來

回推得到的順序是：

G → F → E → B → A

但真正從起點出發應該是：

A → B → E → F → G

所以等 Recursion 全部結束後，再反轉一次：

routes(endNode)
routesNode.reverse()

最後這組資料得到：

Distance = 10
Path = A → B → E → F → G

上一篇做到的是「最短距離是多少」，今天補上 Previous 後，終於也能回答「這條最短路徑到底怎麼走」。

簡單來說，Path Reconstruction 就是從終點開始，沿著 Previous 一路回到起點，再把結果反轉。

完整程式碼

type QueueNode = {
  node: string
  distance: number
}

type TableNode = {
  node: string
  distance: number
  previous: string
}

/** 圖的鄰接表：節點 → [{ 鄰居節點: 距離 }] */
type DijkstraGraph = Record<
  string,
  Record<string, number>[]
>

const dijkstraData: DijkstraGraph = {
  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 }],
  D: [{ A: 7 }, { C: 6 }, { G: 4 }],
  E: [{ B: 1 }, { F: 2 }, { G: 7 }],
  F: [{ B: 5 }, { C: 8 }, { E: 2 }, { G: 3 }],
  G: [{ D: 4 }, { E: 7 }, { F: 3 }],
}

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,
      previous: '',
    })
  }

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

  if (!firstNodeData) {
    return {
      table,
      routesNode: [],
    }
  }

  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
    )

    /** 更新 Distance 與 Previous */
    if (
      tableNode &&
      tableNode.distance > neighborDistance
    ) {
      tableNode.distance = neighborDistance
      tableNode.previous = startNode
    }

    /** 加入等待處理的 Queue */
    q.push({
      node: neighborNode,
      distance: neighborDistance,
    })
  }

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

  /** 接著重複處理 Queue */
  while (q.length > 0) {
    /** 找出 Queue 中 Distance 最小的 Node */
    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

    /** 檢查目前 Node 的所有 Neighbor */
    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
      )

      /**
       * 找到更短的路徑時，
       * Distance 與 Previous 一起更新
       */
      if (
        tableNode &&
        tableNode.distance > totalDistance
      ) {
        tableNode.distance = totalDistance
        tableNode.previous = nextNode.node
      }

      /** 更新 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
    )
  }

  /** 記錄最後找到的完整 Path */
  const routesNode: string[] = []

  /** 從終點透過 Previous 一路回推到起點 */
  function routes(node: string): void {
    if (!node) return

    routesNode.push(node)

    /** 已經回到起點 */
    if (node === startNode) return

    const currentNode = table.find(
      (item) => item.node === node
    )

    routes(currentNode?.previous ?? '')
  }

  /** 確認終點是否可以抵達 */
  const finalEndNode = table.find(
    (item) => item.node === endNode
  )

  if (
    finalEndNode &&
    finalEndNode.distance !== Infinity
  ) {
    routes(endNode)
    routesNode.reverse()
  }

  return {
    table,
    routesNode,
  }
}

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