君の名は

Dijkstra’s algorithm (迪杰斯特拉算法)是一个单源最短路径的算法，即从一个顶点出发到其它顶点的最短路径计算。

图：来自小破站 up 主

最近发现一个挺有意思的 up 主，ID 是 - “笑笑的计算之心”，有想学习算法的同学可以关注下。小姐姐用了 Manim CE 制作了很多经典算法的动画演变过程。同时，也使用了很多《算法导论》里的伪代码，感觉质量还是蛮高的。

算法的基本思路：

将所有节点加入一个集合中 - UnReachSet；
给每个节点添加 key 和 previous 属性，key 表示源点到自己的最小权重，previous 表示上个节点；
初始化所有节点的 key 为无限大，previous 为空；
初始化源点的 key 为 0，因为自己到自己的距离为 0;
循环从 UnReachSet 寻找 key 最小的值，并剔出；
寻找 5 的邻居节点，并进行松弛操作
直到 UnReachSet 为空

Pseudo Code



DIJKSTRA(G,s) {
  UnReachSet = G.V
  set all vertices v.key = ∞
  set all vertices v.previous = ∅
  s.key = 0
  while UnReachSet != ∅
    v = EXTRACT-MIN(UnReachSet)
    for each neighbor u of v
    // Relax edge(v,u)
      if u.key > v.key + weight(v,u)
        u.key = v.key + weight(v,u)
        u.previous = v
}

松弛操作

伪代码中的 Relax edge 其实是一种技术，叫做“松弛操作”

松弛技术是算法导论里的一个概念，目的是对节点间的距离的上界进行收紧，背后有一套复杂的数学论证，对于数学不好的我来说，可以说是完全看不懂：）。那就到这吧

例子：

alt

现在以这个 有向加权图为例子，找到从 A 节点出发到其它节点的最短路径

先写出这个图的邻接矩阵表示

图的邻接矩阵表示


const graph = [
  [0, 2, 4, 0, 0, 0],
  [0, 0, 2, 4, 2, 0],
  [0, 0, 0, 0, 3, 0],
  [0, 0, 0, 0, 0, 2],
  [0, 0, 0, 3, 0, 2],
  [0, 0, 0, 0, 0, 0]
];

代码实现


// 找出dist中的最小值
const extractMinKey = (set) => {
  let minValue = Number.MAX_SAFE_INTEGER;
  let minKey = null;
  Object.keys(set).forEach((k) => {
    if (!set[k].visited && set[k].key < minValue) {
      minValue = set[k].key;
      minKey = k;
    }
  });
  if (minKey) set[minKey].visited = true;
  return minKey;
};

// 接受图的邻接矩阵，源点作为参数
const dijkstra = (graph, src) => {
  const unReachSet1 = {};
  const INF = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < graph.length; i++) {
    unReachSet1[i] = {
      key: INF,
      previous: null,
      visited: false
    };
  }
  unReachSet1[src].key = 0;
  const unReachSet = { ...unReachSet1 };
  while (Object.keys(unReachSet).length) {
    const v = extractMinKey(unReachSet);
    for (let i = 0; i < graph.length; i++) {
      // 找到邻居节点
      if (graph[v] && graph[v][i] !== 0) {
        // 松弛操作
        if (
          unReachSet[i] &&
          unReachSet[v] &&
          unReachSet[i].key > unReachSet[v].key + graph[v][i]
        ) {
          unReachSet[i].key = unReachSet[v].key + graph[v][i];
          unReachSet[i].previous = v;
        }
      }
    }
    if (v) delete unReachSet[v];
  }
  return unReachSet1;
};

console.log(dijkstra(graph, 0));

Code pen
https://codepen.io/jackzong/pen/abKodWe

算法的优缺点

不支持权重为负值

Reference
《学习 JavaScript 数据结构与算法（第 3 版）》
一个漂亮的 up 主

重学数据结构与算法 - 图(Dijkstra's algorithm)