AI 摘要

本文介绍了Dijkstra算法作为一种解决最优路径问题的方法之一。该算法由荷兰计算机科学家Edsger Wybe Dijkstra在1956年发现，主要用于求解赋权图的单源最短路径问题。Dijkstra算法通过类似广度优先搜索的方式，找出给定源点到图中其他结点的最短路径，生成一个最短路径树。尽管算法最初仅适用于查找两个顶点之间的最短路径，在更常见的变体中，固定一个源结点并找到该结点到图中所有其他结点的最短路径。然而，Dijkstra算法并不适用于处理带有负权边的图。算法思路上，首先确定源点，然后逐步扩展已确定的最短路径集合，直至找到源点到所有其他顶点的最短路径。Dijkstra算法的时间复杂度为O(V^2)，可以通过使用优先队列数据结构将其降低至O((V+E)logV)。文章还提供了部分参考文献作为深入了解Dijkstra算法的参考。

算法原理

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最优路径，解决该问题的方法包括Dijkstra算法、Bellman-Ford算法、Floyd算法和SPFA算法等。

Dijkstra 算法，是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法，戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。需要注意的是绝大多数的Dijkstra 算法不能有效处理带有负权边的图。

Dijkstra算法的思路：

  1. 算法初始，将选择的源点s放进集合S;
  2. 无自环的源点s到自己的最短路径为0；
  3. 当顶点v_i不在集合S中时（此时集合S中仍只有源点s，开始进入循环；
  4. 将源点s与点v_i之间的权值赋值给dist[s,v_i]。由于是有向图，所以当源点s不指向任何其他集合S外的顶点时，dist[s,v_i]=\infty。可以理解为此时从源点s出发，暂时是达到不了v_i的。不过随着后面集合S的扩充，从源点s出发一定能够到达所有的顶点。此时第一个循环结束。
  5. 如果集合V-S不是空集，则进入循环；
  6. 选出经过第一个循环后的，在集合V-S中的，且相对于集合S的最短路径中距离最短的那个顶点v_j;
  7. 将这个顶点v_j并入集合S，从而达到扩充集合S的目的；
  8. 将顶点v_j并入集合S之后可能会对其他顶点相对于集合S的最短路径长度有影响，所以进入内循环对有影响的路径分支进行更新，即如果从源点s到我们在第6步选出的顶点v_j的相对于集合S的最短路径的长度再加上顶点v_j到顶点v_j之间的距离\omega_{i,j}还要小于源点s到顶点v_i的相对于集合S的最短路径长度的话，则将源点s到顶点v_i的相对于集合S的最短路径更新为源点s到我们在第6步选出的顶点v_j相对于集合S的最短路径加上顶点v_j到顶点v_i之间的权值\omega_{i,j}。

Dijkstra算法的时间复杂度是o(nm)。其中：

    \[n=|V|, m=|E|\]

分别为赋权有向图中的顶点个数和边的个数。Dijkstra算法的时间复杂度是o(nm)是因为算法总共进行(n-1)步，每一步选出一个具有最小dist[s,\bullet]值的顶点放入集合S中，需要o(m)的时间。
而选择基于堆实现的优先队列数据结构，可将Dijkstra算法的时间复杂度降为o(mlogn)

参考文献

  1. 【路径规划】(1) Dijkstra 算法求解最短路，附python完整代码
  2. 【最短路径问题】—Dijkstra 算法最详解