在介紹 Dijkstra’s Algorithm 前要先說這是最短路徑問題(Shortest Path)中的一種經典演算法，最短路徑問題是能算出在 graph 資料結構中的一個節點(vertex)到其餘各節點距離最短路徑的演算法，針對不同的情境也會有不同對應的演算法出現，例如還有 Bellman-Ford 演算法、Floyd-Warshall 演算法等。

最短路徑問題這類演算法常用在例如 Google map 找出花費最少時間的路徑、飛機搭乘轉機時找出最便宜的轉機路徑等...，而這篇將會以 Dijkstra's Algorithm 為主做介紹。

注意: 使用這個 Dijkstra's Algorithm 的前提是 edge(邊)不得為負數權重。

演算法分析

這邊先推薦一個 youtube 影片 【算法】最短路径查找—Dijkstra算法，將這個演算法透過動畫說明得相當清楚，以下也將拆分多個步驟來說明，Dijkstra's Algorithm 主要就是一種 Greedy 演算法，每次都去找當前離原點距離最小的那一條路。

Step1.

初始化各節點到起點最短路徑的表格，因為節點 0 本身是原點，所以在表格內為 0，而其他點到原點的距離還沒算出來，所以為無限大。

還有它們的前面點也要記錄，所以多一個欄位去記錄某節點在最佳路徑的前一個節點。

首先從節點 0 出發，要找到從節點 0~4 的最短路徑，節點 0 已經訪問過，且是表格當中路徑最短的節點，故打個勾當作標記。

Step2.

更新當前節點和鄰近節點的距離，鄰近節點有 1 & 7，原點到節點有 1 & 7 都比表格紀錄的小，故在表格中更新值上去。

並且節點 1 是表格當中路徑最短且未標記的節點(1, 7 中裡面挑選)，故為它新增標記。

Step3.

接著我們來看當前標記的節點有哪些鄰近的節點，分別是節點 2 & 7，節點 2 到原點的路徑總和是 12，將它加入到表格中，而節點 7 因為路徑總和 4 + 11 > 8，所以不做更新。

接著又再找出表格當中路徑最短的節點(2, 7 中裡面挑選)，故將節點 7 新增標記。

Step4.

繼續看當前標記的節點 7 有哪些鄰近的節點，分別是節點 6 & 8，這兩個節點到原點的距離都比表格中記錄的小，所以更新到表格中。

接著又再找出表格當中路徑最短且未標記的節點(2, 6, 8 中裡面挑選)，故將節點 6 新增標記。

到這裡我們可以推出三個規律去做循環:

1. 先從表格找出離原點最近並且未標記的節點並給予標記
2. 接著查看最新被標記的節點的所有鄰居節點，算出它們的路徑的總和
3. 若路徑總和比當前在表格還小，就去更新表格

Step5.

繼續看當前標記的節點 6 有哪些鄰近的節點，分別是節點 5 & 8，因為節點 5 到原點的距離比表格中節點 5 的紀錄值小，所以更新到表格中。

接著又再找出表格當中路徑最短且未標記的節點(2, 5, 8 中裡面挑選)，故將節點 5 新增標記。

Step6.

繼續看當前標記的節點 5 有哪些鄰近的節點，分別是節點 2 & 3 & 4，繼續將原點到這三個節點的距離更新到表格中。

接著又再找出表格當中路徑最短且未標記的節點(2, 3, 4, 8 中裡面挑選)，故將節點 2 新增標記。

Step7.

繼續看當前標記的節點 2 有哪些鄰近的節點，分別是節點 3 & 5 & 8，從節點 2~3 總距離是 12 + 7，小於原本表格內節點 3 所記錄的 25，所以更新成 19，前面節點也更新成 2。節點 8 的距離也更新成 14，前面節點也更新成 2。

接著又再找出表格當中路徑最短且未標記的節點(3, 4, 8 中裡面挑選)，故將節點 8 新增標記。

Step8.

但是節點 8 的鄰居節點都已經被標記，所以繼續找出表格當中路徑最短且未標記的節點(4, 8 中裡面挑選)，將 3 也新增標記。

Step9.

最後只剩一個節點 4，因此將終點 4 進行標記，然後從終點 4 往前面點推算，0 => 7 => 6 => 5 => 4，這條路就是最短路徑。

實做 Dijkstra 演算法

// 實作一個簡單版的 Priority Queue，更完整可以用 heap 去實作
class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }
  dequeue() {
    return this.values.shift();
  }
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

class WeightedGraph {
  constructor() {
    // 記錄每個節點的相鄰節點
    // ex: { 'A': [{ node: 'B', weight: 10 }] }
    this.adjacencyList = {};
  }
  // 加入節點
  addVertex(vertex) {
    // g.addVertex('A')
    // 結果範例: { 'A': [] }
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  // 加入邊
  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }
  Dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {}; // 記錄各節點到原點的最短路徑
    const previous = {}; // 記錄各節點在最短路徑上的前一個節點
    let path = []; // 記錄最短路徑經過的節點
    let smallest;

    // 初始化最優路徑集合和記錄各節點的前一節點的物件
    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }
    // 初始化後 distances 變成例如: { A: 0, B: Infinity, C: Infinity, D: Infinity, E: Infinity, F: Infinity }
    // previous: { A: null, B: null, C: null, D: null, E: null, F: null }

    // while 迴圈持續執行條件: 還有節點尚未標記
    while (nodes.values.length) {
      smallest = nodes.dequeue().val; // smallest ex: A, B, C...

      // 當前未標記節點等於終點時，產生最短路徑，用 path 陣列儲存
      if (smallest === finish) {
        while (previous[smallest]) {
          // ex: previous 物件為 { A: null, B: A, C: A, D: C, E: F, F: D }
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }
      if (smallest || distances[smallest] !== Infinity) {
        // 訪問當前要標記節點的鄰居，neighbor 為數字，例如 0, 1, 2
        // 打印 this.adjacencyList 的結果見圖，一個物件，A 內的 0, 1 為 neighbor:
        // https://i.imgur.com/hR349Dx.png
        for (let neighbor in this.adjacencyList[smallest]) {

          // 找到某節點的鄰居
          let nextNode = this.adjacencyList[smallest][neighbor];
          // 計算起點到當前節點的距離 + 當前節點到下個節點的距離
          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;

          // 如果當前表格記錄的鄰居節點距離比當前計算出的新的距離長，就去更新表格內的值
          if (candidate < distances[nextNeighbor]) {
            distances[nextNeighbor] = candidate;
            // 更新當前鄰居節點在表格上記錄的前一個節點值
            previous[nextNeighbor] = smallest;
            // 將鄰居節點加入標記行列
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    return path.concat(smallest).reverse();
  }
}

// 以下是建立圖
var graph = new WeightedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);

graph.Dijkstra('A', 'E'); // ["A", "C", "D", "F", "E"]

參考資料

優先佇列

Shortest Path：Intro(簡介)