AI 摘要

**摘要**：本文介绍了Dijkstra最优路径算法的原理和实现过程。Dijkstra算法由荷兰科学家Edsger Wybe Dijkstra于1956年提出，旨在解决赋权图的单源最短路径问题。该算法选择一个源顶点，逐步扩展到图中其他顶点，最终形成一棵最短路径树。算法每次从未访问的顶点中选出距离最小的顶点，并根据该顶点更新其他顶点的最短路径。需要注意的是，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 算法最详解