图的最短路径算法-Dijkstra算法

什么是Dijkstra算法

Dijkstra 的全名叫 Edsger Wybe Dijkstra（艾兹赫尔·韦伯·戴克斯特拉），Dijkstra算法便是由Dijkstra本人发明的求图最短路径的算法，中文名为[迪杰斯特拉]算法。

Dijkstra 算法是一种计算从单个源到所有其他源的最短路径的贪心算法。

Dijkstra算法使用了广度优先搜索解决带权有向图的单源最短路径问题。通过一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。

Dijkstra算法至今仍用在诸多地方，如水浒Q传这类回合制游戏的自动寻路、在百度地图上寻找去某间好吃的餐馆的最短路线，都离不开最短路径算法。

Dijkstra算法详细步骤

以下算法详细步骤图，均来自公众号”程序员小灰”的文章——《漫画:图的”最短路径”问题》

假设有这样一个有向图，我们求从顶点A到其他顶点的最短路径距离是多少。

此时，我们需要构建一个距离表和访问记录表。

距离表的key值对应实例图的顶点，对应的value是从起点A到对应顶点的已知距离。在默认情况下，从起点A到其他顶点的距离都是无穷大。

访问记录表记录着图实例各个顶点的访问情况，默认均为false(即未访问)。

通过顶点A，知道顶点A的相邻顶点有B和C，顶点A到顶点B的距离是5，顶点A到顶点C的距离是2。因为目前距离表中的顶点B和顶点C都是默认的无穷大，此时便可把目前所知的距离(A到B是5，A到C是2)，更新到距离表中，同时将顶点A在访问记录表中记录为已访问。

此时，距离表中，路径最短的顶点是顶点C，则我们从顶点C开始探索，可知顶点C的相邻顶点有D和F(顶点A在访问记录表中为已访问，不需要考虑)。

顶点C到顶点D的距离是6，所以顶点A到顶点D的距离是2+6=8。

顶点C到顶点F的距离是8，所以顶点A到顶点F的距离为2+8=10。

顶点D和顶点F在距离表中均为默认的无穷大，此时便可把上述所得到的距离更新到距离表中，同时将顶点C在访问记录表中记录为已访问。

此时，距离表中，路径最短的顶点是顶点B(顶点A和顶点C在访问记录表中为已访问，不需要考虑)，则我们从顶点B开始探索，可知顶点B的相邻顶点有D和E(顶点A在访问记录表中为已访问，不需要考虑)。

顶点B到顶点D的距离是1，所以顶点A到顶点D的距离是5+1=6。

顶点B到顶点E的距离是6，所以顶点A到顶点E的距离为2+8=11。

顶点A到顶点D的距离6，小于当前距离表中的8，此时我们需覆盖掉原来距离表中顶点D的8，刷新为新值6。

顶点A到顶点E的距离11，顶点F在距离表为默认的无穷大，可以刷新无穷大为已知新距离值11。

同时将顶点B在访问记录表中记录为已访问。

剩下的步骤也如同上部分一样，通过距离表逐个判断图实例顶点的最短路径，迭代刷新，用新路径长度刷掉旧的路径长度，最终得到从起点到任意其他顶点的最短距离：

此时，距离表中，路径最短的顶点是顶点D(顶点A、顶点B和顶点C在访问记录表中为已访问，不需要考虑)，则我们从顶点D开始探索，可知顶点D的相邻顶点有E和F(顶点B和顶点C在访问记录表中为已访问，不需要考虑)。

顶点D到顶点E的距离是1，所以顶点A到顶点E的距离是6+1=7。

顶点D到顶点F的距离是2，所以顶点A到顶点F的距离为6+2=8。

顶点A到顶点E的距离7，小于当前距离表中的11，顶点A到顶点F的距离8，小于当前距离表中的10。

我们此时便可以把距离表中的顶点E距离覆盖为7，顶点F在的距离覆盖为8。

同时将顶点D在访问记录表中记录为已访问。

此时，距离表中，路径最短的顶点是顶点E(顶点A、顶点B、顶点C和顶点D在访问记录表中为已访问，不需要考虑)，则我们从顶点E开始探索，可知顶点E的相邻顶点有G(顶点B和顶点D在访问记录表中为已访问，不需要考虑)。

顶点E到顶点G的距离是7，所以顶点A到顶点G的距离是7+7=14。

顶点G在距离表中仍然是默认的无穷大，我们此时便可以把距离表中的顶点G距离覆盖为14。

同时将顶点E在访问记录表中记录为已访问。

此时，距离表中，路径最短的顶点是顶点F(顶点A、顶点B、顶点C、顶点D和顶点E在访问记录表中为已访问，不需要考虑)，则我们从顶点F开始探索，可知顶点E的相邻顶点有G(顶点C和顶点D在访问记录表中为已访问，不需要考虑)。

顶点F到顶点G的距离是3，所以顶点A到顶点G的距离是8+3=11(路径A-B-D-F-G)。

我们此时便可以把距离表中的顶点G距离覆盖为11。

同时将顶点G在访问记录表中记录为已访问，到此位置，图实例的全部顶点均遍历完毕。

此时将距离表返回，距离表中此时存储的数值，便是顶点A到其他顶点的最短距离。

代码实现

// INF常量保存Number类型的无穷大
const INF = Number.MAX_SAFE_INTEGER;
/**
 * 计算图实例所有顶点中的最小路径顶点的内部函数
 * @param {*} dist 图实例的距离表
 * @param {*} visited 图实例的访问记录表
 * @returns {*} 返回当前图实例中最短路径的顶点下标
 *  */
const minDistance = (dist, visited) => {
  // // 找到当前最短路径顶点作为中转跳点
  let min = INF; // 存储当前最短路径的距离(默认为无穷大)
  let minIndex = -1; // 存储当前最短路径顶点的下标
  for (let v = 0; v < dist.length; v++) { // 遍历图实例的顶点列表
    if (visited[v] === false && dist[v] <= min) { // 如果该顶点没有访问过，且该顶点的最短距离小于等于目前的最短距离
      min = dist[v]; // 更新最短路径的距离
      minIndex = v; // 更新最短路径顶点的下标
    }
  }
  // 找到图实例中所有顶点中最短路径的顶点下标，将其返回
  return minIndex; // 返回图实例中所有顶点中最短路径的顶点(下标)
};
/**
 * 最短路径算法-迪杰斯特拉算法
 * @param {*} graph 需要计算最短路径的图实例
 * @param {*} src 给定的起始顶点
 * @returns {*} 图实例的最短路径
 */
export const dijkstra = (graph, src) => {
  const dist = [];  //创建距离表，存储从起点到每一个顶点的临时距离
  const visited = []; //创建顶点的访问记录表，记录遍历过的顶点
  const { length } = graph;  //图实例的顶点数量
  
  //初始化最短路径表，到达每个顶点的路径代价默认为无穷大，每个顶点的访问记录均为未访问(false)
  for (let i = 0; i < length; i++) {
    dist[i] = INF;
    visited[i] = false;
  }
  dist[src] = 0; // 获取起点，刷新距离表，图实例传入的起始顶点距离为0
  //主循环，重复 遍历最短距离顶点和刷新距离表 的操作
  for (let i = 0; i < length - 1; i++) {  
    const u = minDistance(dist, visited); // 图实例每个顶点都去遍历最短距离顶点，传入图实例的距离表(dist)和访问记录表(visited)
    visited[u] = true; // 当前节点项已经访问完毕，更新当前节点项访问状态为true
    for (let v = 0; v < length; v++) { // //遍历顶点(也就是遍历当前顶点的邻接矩阵)，刷新距离表
      // 如果找到更短的路径，则更新最短路径的值
      if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) { 
        dist[v] = dist[u] + graph[u][v];
      }
    }
  }
  return dist; // 处理完所有顶点后，返回从起始顶点（src）到图中其他顶点最短路径的结果。
};

代码用例

如果有这样一个邻接矩阵图实例

let graph = [
 [0, 2, 4, 0, 0, 0],
 [0, 0, 1, 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]
]; 

使用Dijkstra算法后得到的结果如下:

/**
0 0
1 2
2 4
3 6
4 4
5 6
**/