前言

昨天的 BFS 回答的是「從台北到台中最少要經過幾條路」，或者可以說要經過幾條 edge，小結最後有說，每條 edge 代表同樣的成本時，最少 edge 數才等於最低成本；如果台北直達新竹要 200 元、經桃園卻是 50 加 50 元，只數 edge 就會挑到比較貴的那一條。

今天的舉例會把地圖換成機票路線圖，每段航線都有自己的票價。舉例來說，從台北到札幌，直飛只要搭一班飛機，票價 12000 元；先飛福岡、再經東京轉過去，雖然要搭三班，總票價卻只要 7500 元。轉機比較麻煩，但便宜了 4500 元。

那麼，當每一段的票價都不一樣時，我們要怎麼一步步找出總票價最低的那條路徑呢？今天就來看看 Dijkstra's Algorithm～

最少 edge 數不等於最低票價

一張標上票價的航線圖

先介紹一下今天要用的案例～5 個城市之間有 9 條航線，每條都標著票價（文章的票價都是示範用，不代表真實價格）：

台北 → 大阪  2500      福岡 → 東京  2000
台北 → 福岡  4000      福岡 → 札幌  6000
台北 → 札幌 12000      東京 → 札幌  1500
大阪 → 東京  4500      札幌 → 大阪  5000
大阪 → 福岡  3000

每一條航線就是 Graph 的 edge，票價則是掛在 edge 上的值。航線只往一個方向飛，所以這是一張 Directed Graph；edge 上帶著票價，它同時也是 Weighted Graph。昨天那張地圖兩者都不是，每條路都可以雙向通行、也沒有值，因此問「最少 edge 數」就足夠了。今天要問的則是總票價最低，也就是把沿路每條 edge 上的值加起來，總和最小的那一條路徑。換句話說，昨天的 BFS 處理的是 Unweighted Graph 的最短路徑，今天要找的是 Weighted Graph 上的最短路徑。

這裡還有個前提，票價是有限的數字，而且不會是負的。可以是 0，代表那一段不用錢（可想成優惠價格之類的），但沒有「搭了反而拿回錢」這種航線（也就是沒有負數票價，航空公司不會倒貼錢給你）。

圖 1 每條航線只往一個方向飛，票價標在航線上

把票價放進鄰居名單

Day 24 的 Graph 把鄰居放在 Set 裡，因為那時只需要知道兩個 vertex 之間有沒有 edge。今天每條 edge 還帶著票價，所以鄰居名單改用 Map，key 是鄰居、value 是票價，代表從這個 vertex 到鄰居的票價，航線是單向的，addEdge 只加一邊：

class WeightedGraph {
  constructor() {
    this.adjacency = new Map();
  }

  addVertex(value) {
    if (!this.adjacency.has(value)) this.adjacency.set(value, new Map());
  }

  addEdge(from, to, weight) {
    this.addVertex(from);
    this.addVertex(to);
    this.adjacency.get(from).set(to, weight); // 只加一個方向
  }

  neighbors(v) {
    return [...(this.adjacency.get(v) ?? [])];
  }
}

把 9 條航線加進去之後，neighbors 展開 Map，得到的是一組「鄰居與票價」：

const flights = new WeightedGraph();
flights.addEdge('台北', '大阪', 2500);
flights.addEdge('台北', '福岡', 4000);
flights.addEdge('台北', '札幌', 12000);
flights.addEdge('大阪', '東京', 4500);
flights.addEdge('大阪', '福岡', 3000);
flights.addEdge('福岡', '東京', 2000);
flights.addEdge('福岡', '札幌', 6000);
flights.addEdge('東京', '札幌', 1500);
flights.addEdge('札幌', '大阪', 5000);

console.log(flights.neighbors('台北'));
// [ [ '大阪', 2500 ], [ '福岡', 4000 ], [ '札幌', 12000 ] ]

圖 2 鄰居名單從 Set 換成 Map，value 放的就是那條航線的票價

BFS 找到的是哪一條？

如果先不管票價，只照昨天 BFS 的規則走這張圖，它會怎麼回答「從台北到札幌的最短路徑」呢？台北的鄰居是大阪、福岡、札幌，札幌就在其中，第一輪就被找到，距離是 1 條 edge。BFS 給的答案是直飛，因為它回答的是最少 edge 數，票價多少它不在乎。

可是直飛要 12000 元，而台北經福岡、東京飛到札幌只要 4000 ＋ 2000 ＋ 1500 ＝ 7500 元。同一張地圖上，edge 數最少的那條路徑和總票價最低的那條，並不是同一條。

圖 3 edge 數最少的路徑，總票價不是最低的

把每條路徑都列出來比較？

既然要的是總票價最低，那不如把所有路徑都列出來，一條一條加總再挑最小的？

這張圖上有環，例如札幌→大阪→東京→札幌就繞得回來，但票價不會是負的，繞一圈不會讓總價變低，因此只要看不重複經過同一個城市的路徑就夠了。從台北到札幌這樣的路徑一共有 6 條：

此時若要問從台北到札幌總票價最低的金額，答案就在表裡，7500 元。

這做法本身沒什麼問題，但就算邊產生邊比較，還是得把每一條路徑都走過一遍，當城市和航線一多，路徑的數量會變得更多，運算的複雜度會因此提高。

那這問題該怎麼解呢？有個解法叫 Dijkstra's Algorithm，它不列舉路徑，而是替每個城市記下目前找到的最低票價，一邊往外走一邊修正。

Dijkstra's Algorithm 需要兩張表：目前最低票價與前一站

1. 目前最低票價：lowestPrice

要邊走邊記，第一件事是決定記什麼。我們替每個城市記一個數字：從台北出發到它，目前找到的最低票價。台北自己是 0，因為待在原地不需要搭任何一班飛機。

這份紀錄用 Map，城市當 key。後面都用物件的寫法來示意 Map 裡的內容：

// 從台北到各地的最低票價
{
  '台北': 0,
  '大阪': 2500
}

城市不在 Map 裡，就代表目前還不知道怎麼飛到它；一旦算出過票價，它就有一個數字。Day 26 的 distance 也是這樣用的，差別在今天這個數字之後還可能被改小。

2. 前一站：previousStop

只有票價還不夠。知道「台北到札幌最低 7500 元」和知道「台北到札幌要怎麼飛才會是 7500 元」是兩件事，前者是一個數字，後者是一整條路徑。所以我們還要第二張表，記下以目前這個最低票價抵達某個城市時，它的前一站是誰：

// 以目前的最低票價抵達時，前一站是誰
{
  '大阪': '台北' // 以目前最低票價到大阪時，大阪的前一站是台北
}

起點台北不需要從哪裡飛過來，所以不在這張表裡。兩張表的分工如下：

只想知道票價的話，lowestPrice 一張就夠；要完整路徑的話，兩個資料都需要。

找到更便宜的票價，兩張表一起改

接著是更新的規則。站在某個城市上，沿著它的一條航線看向鄰居，這樣飛過去鄰居的票價是「目前抵達這城市的最低票價 ＋ 要到鄰居這段航線的票價」。如果鄰居還沒有紀錄，或算出來的數字比它現有的紀錄更低，就更新；否則就什麼都不做。

要注意的是，兩張表要一起改。把價格換成更低的那個時，前一站也要換成現在站著的這個城市，因為現在用最低價格抵達該（鄰居）城市的前一站，變成現在站著的城市了；只改價格的話，previousStop 留下的還是舊路徑，最後要回推路徑時就會有錯誤。

圖 4 算出來比較低才更新，而且價格和前一站一起改

下一個處理哪個城市？

更新完鄰居之後，下一個要站到哪個城市上呢？

這是今天和昨天差最多的地方。BFS 用 Queue，先發現的先處理，要處理的順序在發現當下就排好了；今天則是在所有「有紀錄、但還沒確定」的城市裡，挑目前票價最低的那一個，這些城市後面就叫它們「候選」。挑中之後，它的票價就不再更動，我們說它已經「確定」。等等寫的程式會用 candidates Array 保存候選城市，用 settled Set 記下已確定的城市。第一次發現城市時加入候選，被選中時再從候選移除；之後若找到更低的票價，只改紀錄，不必再加入一次。

因此每個城市會經過兩種狀態：第一次被算出票價，是已發現；被選中為下一個城市而且不再更動，是已確定。昨天這兩件事是同時發生的，第一次發現就定案；今天中間可能隔著好幾輪，而且紀錄在這段期間還會被改小。

講了這麼多規則，Dijkstra's Algorithm 到底是什麼？先給一句話定義吧～

Dijkstra's Algorithm 在 weight 非負的 Graph 上，為每個 vertex 記下從起點到它目前最低的已知 weight 總和；每一輪從還沒確定的 vertex 中選出數值最低的那個，把它的結果確定下來，再沿著它的 edge 更新鄰居的紀錄與前一站。

從台北出發，一輪一輪找到札幌

看了上面的規則可能感覺十分模糊，接下來就來實際走一次流程吧～

開始之前，lowestPrice 只有台北的 0，previousStop 是空的，candidates 只有台北，settled 還沒有任何城市：

lowestPrice = {
  '台北': 0
}

previousStop = {}

candidates = ['台北']
settled = new Set()

起點台北是第一個要處理的城市。每一輪把選出的城市移出候選、加入 settled，再看它的航線，最後從剩下的候選選出下一輪的城市。候選 Array 依加入順序保存城市，沒有按票價排序。

五輪的選取與更新

第 1 輪：選出台北（0 元）

台北是唯一有紀錄的城市，所以第一輪站在台北，看它飛出去的三條航線。這三個城市都還沒有紀錄，大阪於是記 2500、福岡記 4000、札幌記 12000，前一站都是台北。

lowestPrice = {
  '台北': 0,
  '大阪': 2500, // 新增
  '福岡': 4000, // 新增
  '札幌': 12000 // 新增
}

previousStop = {
  '大阪': '台北', // 新增
  '福岡': '台北', // 新增
  '札幌': '台北'  // 新增
}

candidates = ['大阪', '福岡', '札幌']
settled = new Set(['台北']) // 新增台北

圖 5 第 1 輪確定台北，三個鄰居第一次拿到票價

第 2 輪：選出大阪（2500 元）

台北的航線都看完了，下一步要站到哪個城市呢？候選是大阪 2500、福岡 4000、札幌 12000，最低的是大阪，所以這一輪站在大阪。

大阪→東京 算出 2500（台北到大阪的最低票價）＋ 4500（大阪→東京 的票價）＝ 7000，東京第一次有紀錄，前一站是大阪。大阪→福岡 同樣算出 2500 ＋ 3000 ＝ 5500，但福岡現在的紀錄是 4000，5500 並沒有比較低，福岡的票價和前一站都不動。

lowestPrice = {
  '台北': 0,
  '大阪': 2500,
  '福岡': 4000,
  '札幌': 12000,
  '東京': 7000 // 新增
}

previousStop = {
  '大阪': '台北',
  '福岡': '台北',
  '札幌': '台北',
  '東京': '大阪' // 新增
}

candidates = ['福岡', '札幌', '東京']
settled = new Set(['台北', '大阪']) // 新增大阪

圖 6 第 2 輪確定大阪，東京第一次有紀錄，福岡不更新

第 3 輪：選出福岡（4000 元）

大阪的航線都看完了，下一步要站到哪個城市呢？剩下的候選是福岡 4000、東京 7000、札幌 12000，最低的是福岡，所以這一輪站在福岡。

福岡→東京 算出 4000 ＋ 2000 ＝ 6000，比東京原本的 7000 低，於是東京改成 6000、前一站從大阪換成福岡。福岡→札幌 算出 4000 ＋ 6000 ＝ 10000，比 12000 低，札幌也改成 10000、前一站從台北換成福岡。

lowestPrice = {
  '台北': 0,
  '大阪': 2500,
  '福岡': 4000,
  '札幌': 10000, // 原本是 12000
  '東京': 6000   // 原本是 7000
}

previousStop = {
  '大阪': '台北',
  '福岡': '台北',
  '札幌': '福岡', // 原本是台北
  '東京': '福岡'  // 原本是大阪
}

candidates = ['札幌', '東京']
settled = new Set(['台北', '大阪', '福岡']) // 新增福岡

圖 7 第 3 輪確定福岡，東京與札幌的紀錄同時被改小

第 4 輪：選出東京（6000 元）

剩下的候選只有東京 6000 和札幌 10000，最低的是東京，所以這一輪站在東京。

東京→札幌 算出 6000 ＋ 1500 ＝ 7500，又比 10000 低，札幌改成 7500、前一站換成東京。

lowestPrice = {
  '台北': 0,
  '大阪': 2500,
  '福岡': 4000,
  '札幌': 7500, // 原本是 10000
  '東京': 6000
}

previousStop = {
  '大阪': '台北',
  '福岡': '台北',
  '札幌': '東京', // 原本是福岡
  '東京': '福岡'
}

candidates = ['札幌']
settled = new Set(['台北', '大阪', '福岡', '東京']) // 新增東京

圖 8 第 4 輪確定東京，札幌再被改小一次

第 5 輪：選出札幌（7500 元）

只剩札幌一個候選，這一輪站在札幌。

札幌只有一條飛回大阪的航線，而大阪已經確定，直接跳過，連價格都不用算。這一輪 lowestPrice 和 previousStop 都沒變動，settled 多了札幌，candidates 則移除了札幌，已經沒有候選城市，流程結束，這時的內容就是最後的結果：

lowestPrice = {
  '台北': 0,
  '大阪': 2500,
  '福岡': 4000,
  '札幌': 7500,
  '東京': 6000
}

previousStop = {
  '大阪': '台北',
  '福岡': '台北',
  '札幌': '東京',
  '東京': '福岡'
}

candidates = []
settled = new Set(['台北', '大阪', '福岡', '東京', '札幌']) // 新增札幌

圖 9 第 5 輪確定札幌，最低票價的路徑是台北→福岡→東京→札幌

第一次找到的票價，不一定是最低的

回頭看札幌的紀錄，它從 12000、10000 到 7500，改了兩次。東京也從 7000 變成 6000。如果照昨天的做法，第一次發現就把答案記下來，那麼第一輪就會回報 12000，而那是 6 條路徑裡最貴的一條。

因此終點第一次被發現時不能直接回傳，要等到它在所有還沒確定的城市裡票價最低、被選出來的那一刻才算數。這兩天的差別整理如下：

為什麼被選出的城市，票價就能確定？

先看第 3 輪的福岡

第 3 輪選出福岡、把 4000 確定下來的時候，憑什麼保證之後不會再冒出更便宜的飛法？

首先先說，今天沒有 Queue，也沒有「第幾層」這件事。昨天能說「Queue 裡的紀錄由前到後不會變小」，是因為每條 edge 都代表同樣的一步；今天的紀錄還會被改小，昨天 BFS 的說法不適用於今天的 Weighted Graph。

現在我們直接看第 3 輪開始時的狀態。已經確定的是台北 0 和大阪 2500，紀錄裡還有福岡 4000、東京 7000、札幌 12000。假設真的有一條更便宜的飛法能到福岡。這條飛法從台北出發，途中可能先經過同樣已確定的大阪，但福岡不在這兩個城市裡，所以它總有一步要離開台北和大阪。

離開的那一步，出發地一定是台北或大阪，目的地則是還沒確定的城市，台北飛大阪不算，因為大阪也已確定。而這條飛法飛到台北或大阪時，花費不會比它們已確定的 0 和 2500 還低，這一步落地時至少是以下 4 種之一：
(1) 台北直飛福岡：0 ＋ 4000 ＝ 4000
(2) 大阪飛福岡：2500 ＋ 3000 ＝ 5500，也就是第 2 輪算過、因為不夠低而沒有更新的那一筆
(3) 大阪飛東京：2500 ＋ 4500 ＝ 7000
(4) 台北直飛札幌：0 ＋ 12000 ＝ 12000

這 4 種裡最低的是 4000，不管走哪一種，只要離開已確定的城市，落地時就已經花掉至少 4000 元。接下來還要再搭幾班飛機才到得了福岡，而票價不會是負的，總價只會增加或持平，不可能回頭低於 4000 元。福岡的 4000 因此不會再被改小。

圖 10 跨出已確定城市的四種落地，最低就是 4000

這段推理的依據來自兩件事：

1. 選取的規則：我們挑的是所有未確定城市裡紀錄最低的那個，因此其他候選的紀錄都不會低於它
2. 票價非負：一條路徑往後延長，總價只會增加或持平

每一輪開始前要維持的三件事

剛才只以福岡這一輪為例說明，那城市更多、航線更複雜時也一樣嗎？Day 04 介紹過的 Loop Invariant 一樣可拿來驗證看看，先寫下每一輪開始前應該成立的性質，再分成 Initialization、Maintenance、Termination 三步確認它們。以下說的「紀錄」，都是指城市在 lowestPrice 裡的票價，「有紀錄」就是 lowestPrice 裡已經有這個城市。

程式會在上一輪結尾選好下一個城市，下一輪開頭才把它加入 settled；第一輪則直接指定起點。所以下面的「每一輪開始前」，指的是已選好目前城市、但還沒把它標記為確定的時候。選好之後到下一輪開始之間，票價紀錄沒有再變動。

在每一輪確定目前城市之前：

1. 每個有紀錄的城市，那個數字都是某一條實際飛法的總票價，前一站也是那條飛法上的前一站。
2. 每個已確定城市的紀錄，就是從起點到它的最低總票價。
3. 每個已確定城市的航線都已經檢查過，它的鄰居該有的紀錄都有了。

第一件事保證紀錄不是憑空的數字，第二件事保證確定之後不會再更動，第三件事則把「已確定」和「鄰居有沒有拿到紀錄」接起來。

Initialization：第一輪開始前成立嗎？

第一輪開始前，只有起點有紀錄，0 就是待在原地的總票價，第一件事成立；還沒有任何城市被確定，後兩件事沒有東西要檢查，自然也成立。

Maintenance：這一輪成立，下一輪還成立嗎？

假設這一輪開始時三件事都成立，把已選好的目前城市叫做 u，它在 lowestPrice 裡的票價叫做 r。候選名單從起點開始，城市第一次有紀錄時加入，確定時才移除，所以有紀錄、還沒確定的城市都在名單裡，不會漏掉。u 是這份名單的最低者，因此 r 就是所有候選中最低的紀錄。

先看第二件事，也就是 r 就是從起點到 u 的最低總票價。第一輪選出的一定是起點，它的紀錄是 0，而票價非負，不可能有更低的走法，下面看的是第二輪之後，這時起點已確定了。先反過來假設有一條到 u 的路徑，總票價比 r 還低，再沿著它從起點往後看：

1. 一定找得到第一個還沒確定的城市 X。 起點已經確定，u 還沒確定，所以這條路徑上一定有一個城市，是從已確定變成還沒確定的第一個，把它叫做 X。X 可以就是 u，也可以是更前面的城市（昨天證明 BFS 時用的是同一個找法）。
2. X 的前一站 P 已經確定，紀錄也是對的。 「第一個」沒確定的 X 保證了排在 X 前面的城市全都已確定，P 就是其中最後一個。照第二件事，P 的紀錄就是從起點到 P 的最低總票價，因此這條假設路徑走到 P 為止，花的錢不會比 P 的紀錄少。
3. X 的紀錄不會高於這條路徑走到 X 為止的花費。 照第三件事，P 已經確定，它的航線都檢查過了。檢查 P→X 時算出「P 的紀錄 ＋ P→X 的票價」，X 如果還沒有紀錄或原本的紀錄比它高，就改成它，否則維持不動；之後紀錄只會被改小，所以 X 的紀錄不會高於這個價格。而第 2 步說這條路徑走到 X 為止不會比它便宜。
4. 走到 X 為止的花費比 r 低。 票價非負，從 X 再往後飛只會讓總價變大或持平，走到 X 為止的花費不超過整條路徑的總票價，而整條路徑一開始就假設比 r 低。
5. 矛盾。 這樣就得到一個還沒確定、紀錄卻低於 r 的城市 X，但 u 之所以被選出，正是因為它的紀錄是所有未確定城市裡最低的。

所以那條更便宜的路徑不存在；而照第一件事，r 自己又是某條實際飛法的總票價，兩邊合起來，r 就是到 u 的最低總票價。

對照剛才的第 3 輪：u 是福岡、r 是 4000，X 就是那條飛法離開台北和大阪之後第一個落地的城市，第 3 步的價格則是圖 10 裡那四個落地金額。那裡是列出四種可能，這裡則是把同一件事寫成對任何一張 graph 都成立的形式。

票價剛好是 0 的那段也沒有例外，加上去不會改變總和，上面那句「不超過」仍成立。

補充：0 與加法的單位元素

0 加上去不改變總和，是因為它是加法的單位元素。這剛好可以連結到去年 FP 系列的 [Day 15] 初探 Monoid：組合的力量～

圖 11 假設路徑上第一個還沒確定的城市，紀錄會低於 r

第一件事在更新的時候就維持住了，新的紀錄是「目前城市的紀錄 ＋ 那段航線票價」，而目前城市的紀錄本來就對應一條實際飛法，後面接上這一段仍然是一條實際飛法，前一站也跟著指向它。第三件事則來自這一輪做的事，選出 u 之後，我們把它的航線全部看過一遍，已經確定的鄰居直接跳過，因為它們的紀錄不會再變小，剛才那段推理就是理由；其餘鄰居該更新的都更新了。下一輪開始時，三件事都還成立。

Termination：結束時得到什麼？

每一輪都會確定一個城市，城市數量有限，流程一定會結束。結束的條件是沒有候選城市可選，而候選指的是「有紀錄、還沒確定」，因此結束時只要有紀錄就一定已經確定，照第二件事，那個紀錄就是最低總票價。

剩下要確認的是：會不會有城市明明飛得到，卻從頭到尾都沒有紀錄？假設真的有，就沿著一條從起點通往它的路徑，找出第一個沒有紀錄的城市，把它叫做 Y。起點的紀錄是 0，所以 Y 不會是起點，它前面一定還有一站，而那一站是路上最後一個有紀錄的城市。結束時有紀錄就代表已經確定，照第三件事，已確定城市的航線都檢查過了，鄰居也都拿到紀錄，那身為它鄰居的 Y 就應該有紀錄才對，和一開始的假設矛盾。飛得到的城市因此最後都有紀錄、也都已經確定；至於飛不到的城市，從頭到尾都不會進到 lowestPrice 裡。

如果票價可以是負數呢？

上述整段推理裡，只有一步用到「票價非負」：路徑往後延長，總價不會變低。如果這一步不成立，會發生什麼事？

機票不會有負的票價，所以這裡換成三個點來看，A、B、C 之間的 weight 分別是：

• A→B 2
• A→C 5
• C→B −4

從 A 出發，第一輪確定 A，B 記 2、C 記 5；第二輪 B 的 2 是最低的，於是 B 被確定在 2。但實際上 A→C→B 的總和是 5 ＋ (−4) ＝ 1，比 2 更低，只是它得先走一段比較貴的 A→C，才能拿到後面那段負的 weight。

圖 12 先走比較貴的一段，反而換到更低的總和

這就是 Dijkstra's Algorithm 不能用在負 weight 上的原因，被選出時的最低，不再保證是最終的最低。weight 真的有負數時，要改用允許負 weight 的演算法，例如 Bellman-Ford。

只找一個終點時，什麼時候可以停？

如果只想知道台北到札幌，其實不必等到所有城市都確定。札幌被選為最低的未確定城市時，它的紀錄就已經是最低總票價，這時可以直接停下來。反過來說，想要起點到所有可達城市的最低票價，就一直跑到沒有候選城市為止。

不過能停的只有這一刻。終點第一次拿到紀錄時不能停，因為那個數字之後還可能被改小：札幌在第 1 輪就拿到 12000，當下就回傳的話，答案會比真正的 7500 多了 4500 元，而它要到第 5 輪被選出來，才能確定不會再改。

沿著前一站找回完整路徑

從札幌往回查

lowestPrice 告訴我們 7500，但路徑要靠 previousStop 才會知道。

要怎麼做呢？要從最後一站札幌開始往回查，札幌的前一站是東京，東京的前一站是福岡，福岡的前一站是台北，回到起點就停。把這一串反過來，就是台北→福岡→東京→札幌，這就是最低票價的路徑。

圖 13 從終點沿前一站回推，反轉之後就是完整路徑

札幌的前一站在過程中換過兩次，從台北換成福岡、再換成東京，每一次都跟著價格一起換。如果當初只改價格、沒有改前一站，現在回推出來的會是第 1 輪的那班直飛，和 7500 這數字無法對上。

BFS 也能用同一種紀錄還原路徑

昨天只算出最少 edge 數，沒有給出實際走的是哪一條路徑，如果要知道實際走的路徑，一樣可用這張表，BFS 在第一次發現一個城市時，把當時正在處理的城市記成它的前一站，最後同樣從終點往回走再反轉。

差別在於是否會被修改。BFS 第一次發現就定案，前一站寫下去就不會再改，今天這張表則會隨著更低的票價被改寫。

來寫寫看 Dijkstra's Algorithm 的程式

在寫實際程式前，先看一下大致的流程圖如下：

圖 14 Dijkstra's Algorithm 的流程示意圖

Dijkstra 程式碼

把前面的規則寫成程式，除了兩張表，還需要候選城市的 Array 與已確定城市的 Set。dijkstra 接收航線圖、起點與終點，最後回傳最低票價和完整路徑；起點或終點不存在、或是飛不到終點時，回傳 null。

function dijkstra(graph, start, destination) {
  if (!graph.adjacency.has(start) || !graph.adjacency.has(destination)) return null;

  const lowestPrice = new Map(); // 記錄最低已知票價
  const previousStop = new Map(); // 取得這個票價的前一站

  let candidates = [start]; // 等待處理的城市
  const settled = new Set(); // 已經確定的城市

  // 待在起點不花錢，第一輪從起點開始
  lowestPrice.set(start, 0);
  let current = start;

  while (current !== null) {
    // 確定目前城市，並把它從候選名單移除
    settled.add(current);
    candidates = candidates.filter(city => city !== current);

    // 檢查目前城市飛出去的每一條航線
    for (const [next, fare] of graph.neighbors(current)) {
      if (settled.has(next)) continue;

      // 第一次發現這個城市時才加入候選
      if (!lowestPrice.has(next)) candidates.push(next);

      // 經過目前城市到達鄰居，總票價是多少？
      const priceThroughCurrent = lowestPrice.get(current) + fare;

      // 還沒有票價紀錄，或這次的飛法更便宜，就一起更新兩張表
      if (!lowestPrice.has(next) || priceThroughCurrent < lowestPrice.get(next)) {
        lowestPrice.set(next, priceThroughCurrent);
        previousStop.set(next, current);
      }
    }

    // 選出最低票價的候選城市，findCheapestCity 的定義見下方
    current = findCheapestCity(candidates, lowestPrice);
  }

  if (!lowestPrice.has(destination)) return null; // 終點沒有票價紀錄，代表從起點到不了

  return {
    price: lowestPrice.get(destination),
    // 沿前一站還原 start 到 destination 的路徑，buildPath 的定義見下方
    path: buildPath(previousStop, start, destination)
  };
}

程式裡的四份資料

先看函式一開始建立的四份資料，它們各自負責的東西如下：

settled 用 Set，是因為處理鄰居時只需要查「這個城市確定過了嗎」。candidates 則要讓我們逐一比較票價、選出最低的城市，先用 Array 就能寫出這流程。Array 裡只放城市，票價仍從 lowestPrice 查，票價改低時不用再改一份副本。

起點的票價先記成 0，也放進候選名單。因為起點是唯一的候選，所以直接把它指定給 current，開始第一輪。

確定目前城市，再檢查它的鄰居

while 在 current 還有城市時繼續執行。每輪先做這兩件事：

settled.add(current);
candidates = candidates.filter(city => city !== current);

目前城市已經被選為最低者，票價可以確定了，所以加入 settled。filter 留下其他城市，把目前城市從候選名單移除，後面的選取就不會再選到它。

接著檢查目前城市的每一個鄰居。已經確定的鄰居直接跳過；其他鄰居如果還沒有票價紀錄，代表是第一次發現，就加入候選：

if (settled.has(next)) continue;
if (!lowestPrice.has(next)) candidates.push(next);

為什麼要看 lowestPrice.has(next)？因為「還沒確定」的城市可能早就在候選名單裡了。例如第 2 輪從大阪看到福岡時，福岡已經在第 1 輪加入過；第 3 輪從福岡看到東京時，東京也已在第 2 輪加入過。它們都還在等候，只需要比較票價，不必重新排進名單。這個判斷放在寫入票價之前，每個城市就只會加入一次。

比較經過目前城市到鄰居的票價

接下來的 priceThroughCurrent，就是假設經過目前城市、再飛到鄰居時的總票價：

const priceThroughCurrent = lowestPrice.get(current) + fare;

第 3 輪處理福岡→東京時，這裡算的是 4000 ＋ 2000 ＝ 6000。再和東京原本的 7000 比較，新的數字更低，所以一起改票價和前一站：

if (!lowestPrice.has(next) || priceThroughCurrent < lowestPrice.get(next)) {
  lowestPrice.set(next, priceThroughCurrent);
  previousStop.set(next, current);
}

如果鄰居還沒有紀錄，這就是目前唯一知道的飛法，直接記下來；如果已有紀錄，就只在新票價更低時更新。東京仍然留在 candidates 裡，等到選下一個城市時，查到的就會是更新後的 6000。

從候選裡選下一個城市

目前城市的航線都檢查完後，就呼叫 findCheapestCity 選出下一個要處理的城市：

current = findCheapestCity(candidates, lowestPrice);

這個小函式接收候選名單與票價表，逐一比較後回傳最低票價的城市，沒有候選時回傳 null：

function findCheapestCity(candidates, lowestPrice) {
  let cheapest = null;

  for (const city of candidates) {
    // 第一個候選先記下來，之後遇到票價更低的再換掉
    if (cheapest === null || lowestPrice.get(city) < lowestPrice.get(cheapest)) {
      cheapest = city;
    }
  }

  // 沒有候選城市時回傳 null
  return cheapest;
}

cheapest 一開始是 null，遇到第一個候選時先記下來，後面只在票價更低時換掉。它記的是城市，比較時才到 lowestPrice 查票價；候選名單為空時，迴圈不會執行，回傳 null。

第 3 輪結束時，候選 Array 是 ['札幌', '東京']，札幌排在前面，但東京的 6000 比札幌的 10000 低，所以回傳東京。下一輪會確定它並檢查它的航線。

如果候選名單已經空了，函式回傳 null，current 也變成 null，外層 while 就會結束。這時兩張表已經保存從起點到所有可達城市的最低票價與前一站，最後再用它們找出指定終點的路徑。

從終點往回組出路徑

如果終點沒有票價紀錄，代表飛不到，dijkstra 直接回傳 null。確認有紀錄後，才呼叫 buildPath，把前一站表、起點與終點交給它，取得完整路徑。這個小函式把前面說的回查流程寫成程式：

function buildPath(previousStop, start, destination) {
  const path = [];
  let currentStop = destination;

  // 從終點沿著前一站往回找，把城市逐一放進路徑
  while (currentStop !== start) {
    path.push(currentStop);
    currentStop = previousStop.get(currentStop);
  }

  // 補上起點，再反轉成從起點到終點的順序
  path.push(start);
  return path.reverse();
}

currentStop 從札幌開始，每次先把城市放進 path，再用 previousStop.get(currentStop) 查前一站，依序放入札幌、東京、福岡。接著查到台北，迴圈就停下來。因為停止時還沒把起點放進去，所以最後補上 path.push(start)，再用 reverse() 反轉，就得到台北→福岡→東京→札幌。

起點和終點相同時，迴圈一次也不會執行，最後只放入起點。這個函式只負責還原已知可達的路徑，是否飛得到終點由 dijkstra 在呼叫前確認。

用航線圖執行一次

將上面的函式都定義好後，呼叫看看：

console.log(dijkstra(flights, '台北', '札幌'));
// { price: 7500, path: [ '台北', '福岡', '東京', '札幌' ] }

和前面推演的結果一致。只想知道票價就取回傳結果的 price，要完整路徑就取 path。如果只需要一個終點，可以在 settled.add(current) 之後判斷 current 是不是 destination，是的話就 break，結果不會改變。

起點就是終點、到不了的城市

還有幾種邊界情況要處理。起點和終點相同時，第一輪就會選出起點並確定它，回傳 0 和只有起點的路徑：

console.log(dijkstra(flights, '台北', '台北'));
// { price: 0, path: [ '台北' ] }

如果終點從起點飛不到，lowestPrice 裡不會有它的紀錄，程式回傳 null。這裡不能直接沿著 previousStop 往回推，因為查不到的前一站會是 undefined，回推的迴圈永遠碰不到起點：

flights.addEdge('沖繩', '大阪', 3000); // 只有從沖繩飛出去，沒有從其他地方飛進來

console.log(dijkstra(flights, '台北', '沖繩')); // null

起點或終點根本不在這張圖裡，同樣回傳 null。另外，兩條路徑票價相同時，priceThroughCurrent < lowestPrice.get(next) 用的是嚴格小於，保留先找到的那一條；而票價剛好 0 的航線也不會出錯，因為判斷有沒有紀錄用的是 lowestPrice.has(next)，不是拿數值當條件。

要花多少成本？

每一輪都要掃過所有候選城市

令 V 是 Graph 的城市數、E 是航線數，這一段看的是外層 while 和它裡面掃候選的工作。

外層的 while 每跑一輪就確定一個城市，而每個城市只會被確定一次，因此最多跑 V 輪。一輪裡面和候選有關的工作有兩件：filter 要把候選名單整個掃過一遍，才能移除目前這個城市；findCheapestCity 也要整個掃過一遍，才知道誰的票價最低。而每個城市只在第一次發現時加入 candidates，名單最多 V 筆，這兩件事各是 O(V)。

外層最多 V 輪，每一輪裡面最多 O(V)，相乘就是 O(V²)。

每條航線只會被檢查一次

另一半的工作是更新鄰居。每個城市只會被確定一次，而只有在確定的那一輪才會檢查它的航線，所以每條航線最多被檢查一次，全部加起來是 O(E)。

最後的路徑還原最多經過 V 個城市，再反轉一次，合計 O(V)。兩邊的主要工作相加，這份實作的時間複雜度是 O(V² + E)，還原路徑的 O(V) 被吸收在裡面。今天的航線是單向的，同一個方向最多一條，E 最多是 V(V − 1)，代進去之後也可以直接寫成 O(V²)。Day 24 那張地圖算的是 V(V − 1) ÷ 2，因為那裡的每條路都雙向通行，一條 edge 會被兩端各算一次。

額外需要多少空間

沿用 Day 25 的 Auxiliary Space 算法，不計輸入的 Graph，也不計要回傳的路徑。lowestPrice、previousStop、candidates、settled 各最多存 V 筆。filter 建立新候選 Array 時，舊的和新的最多各有 V 筆；neighbors() 回傳的鄰居名單也最多 V 筆，而且同時只處理一份，因此額外空間是 O(V)；回傳的路徑最多 V 個城市，一起算進去仍然是 O(V)。

找最低票價這一步好像有點熟悉...？我們見過的 Priority Queue

今天的實作是用 Array 保存候選，再用線性掃描找最低票價，這樣寫是為了讓流程比較清楚好懂，但找最低這件事聽起來有點熟悉...？在 Day 22 已經出現過，我們不需要把候選城市完整排好，只需要隨時指出目前最低的那一個，這正是 Priority Queue 做的事，Heap 則是它常見的實作。Day 22 的急診室案例是數字越大越優先，今天要的則是最低的票價，兩者結構相同，只是規則的方向相反。

將候選的資料換成 Priority Queue 來儲存後，每一輪取出最低的那一步會變快，但票價被改小時，也得讓它知道某個城市的優先程度變了，Day 22 有說明過，在 Heap 裡找出一個指定值本身就要 O(N)，也有提到 Node.js 的做法會用 setPosition 來優化，把每筆資料在 Heap 裡的位置記下來，不必線性找過去。所以這件事怎麼處理會影響整體成本，不同實作方式要各自分析，這裡就不再說明通用的複雜度了～

Graph 小小總結

這幾天講了很多 Graph 的東西，將這些內容整理如下：

Bellman-Ford 的做法今天就不展開說明，有興趣可以再去查查相關資料～

延伸：路由器怎麼挑一條路

之前上小賴老師的「給網站工程師的網路課」時，講到路由器怎麼決定下一步要把封包交給誰，這其實就是在找最短路徑：到同一台機器通常不只一條路可以走，而每條鏈路都被設定了一個成本，路由器要挑的是總成本最低的那一條。

常見的路由協定 OSPF (Open Shortest Path First) 用的就是今天這套挑法。同一個區域裡的路由器會互相交換鏈路資訊，每台機器再以自己為根，把手上的資料建成一張 Graph，然後從候選裡挑出成本最低的加進來、接著看它的鄰居，一路長成一棵最短路徑樹，形狀就像今天的 previousStop 把每個目的地的前一站接起來那樣。

不過這只是 OSPF 在同一個區域內的算法，其他路由協定不一定這樣做，這棵樹也不是每個封包到達時重算一次，而是鏈路狀態有變化時才重新計算。OSPF 完整規則寫在 RFC 2328 裡，有點複雜我也沒完全理解，只是剛好延伸想到><

小結

小小總結一下今天對 Dijkstra's Algorithm 的認識～

• 為什麼需要 Dijkstra's Algorithm？ BFS 數的是 edge 數，每段成本不一樣時，edge 數最少的路徑不一定總成本最低。要比較的是沿路 weight 的總和，就需要另一種決定順序的方式。換句話說，BFS 解的是 Unweighted Graph 的最短路徑，只看 edge 數；今天要解的是 Weighted Graph 上的最短路徑，看的是 weight 的總和。
• 用了 Dijkstra 之後差在哪？ 每個城市有「目前最低的已知票價」和「這個價格從哪一站來」兩筆紀錄，價格可以被改小，直到它在未確定的城市裡最低而被選出，才確定下來。跑完之後不只知道 7500，還能沿著前一站還原出台北→福岡→東京→札幌。
• Dijkstra's Algorithm 到底是什麼？ 每一輪選出未確定城市裡紀錄最低的那個並確定它，再沿著它的 edge 更新鄰居的紀錄與前一站。它成立的前提是 weight 非負，選取規則保證其他候選都不會更低，非負保證路徑往後延長只會增加或持平。

實際使用時，還可以記住幾件事～

• 終點第一次被發現時不能直接回傳，要等它被選為最低的未確定城市
• weight 有負數時不能用 Dijkstra，要改用允許負 weight 的演算法
• 取出最低候選的方式決定了成本，線性掃描是 O(V² + E)，Priority Queue 改善的是這一步

在每條 edge 都一樣的地圖上，Queue 的順序剛好就是紀錄由小到大的順序，因此昨天的 BFS 不需要比較數值，而如果是今天的案例，當票價不同時，我們就要自己找出順序。

（Dijkstra 真的好難解釋🫠，我覺得 A Common-Sense Guide to Data Structures and Algorithms 這本書在介紹 Dijkstra 時蠻清楚好懂的，推薦大家去讀看看！）

圖表說明：本文圖表由作者整理，並使用 Claude Code 協助繪製；內容與數據由作者確認。

Reference

• Master the Coding Interview: Data Structures + Algorithms
• 《A Common-Sense Guide to Data Structures and Algorithms, Second Edition》
• RFC 2328：OSPF Version 2