最短路径问题几乎是每个计算机专业学生的必学知识点，相关的算法也比较多样，但其中最经典的肯定是由荷兰计算机科学家，1972年图灵奖得主Edsger Dijkstra于1959年发布的Dijkstra's Algorithm。
最短路径问题简单来说就是给定一个图和图中的一个源顶点，找到从源到给定图中所有顶点的最短路径。
举个简单的例子：
下面这张图，给定起点为src = 0
正确的输出结果应为：0 4 12 19 21 11 9 8 14
解释：
- 0 到 1 的距离 = 4.
- 0 到 2 的最小距离 = 12. 0->1->2
- 0 到 3 的最小距离 = 19. 0 ->1->2->3
- 从 0 到 4 的最小距离 = 21. 0->7->6->5->4
- 从 0 到 5 的最小距离 = 11. 0->7->6- >5
- 从 0 到 6 的最小距离 = 9。 0->7->6
- 从 0 到 7的最小距离 = 8。 0->7
- 从 0 到 8 的最小距离 = 14。 0->1->2 ->8
具体步骤为：
- 创建一个集合sptSet（最短路径树集合），跟踪包含在最短路径树中的顶点，即计算并最终确定其与源的最小距离。最初，这个集合是空的。
- 为输入图中的所有顶点分配一个距离值。将所有距离值初始化为正无穷。将源顶点的距离值指定为 0，以便首先获取它。
- 虽然sptSet不包括所有顶点
- 选择一个在sptSet中不存在且具有最小距离值的顶点u 。
- 将u添加到sptSet集合中
- 然后更新u的所有相邻顶点的距离值。
- 要更新距离值，必须遍历所有相邻顶点。
- 对于每个相邻的顶点v，如果u的距离值（到源）与边uv的权重之和小于v的距离值，则更新v的距离值。
注意：我们使用布尔数组 sptSet[] 来表示 SPT 中包含的顶点集。如果值 sptSet[v] 为true，则顶点 v 包含在 SPT 中，否则不包含。数组 dist[] 用于存储所有顶点的最短距离值。
还是以上方的插图为例：
以0为起点
步骤1:
- 集合sptSet最初是空的，分配给顶点的距离是 {0, INF, INF, INF, INF, INF, INF, INF}，其中INF表示无限。
- 现在选择具有最小距离值的顶点。选择顶点 0，将其添加在sptSet中。所以sptSet变成 {0}。之后更新其相邻顶点的距离值。
- 0 的相邻顶点分别是 1 和 7。1 和 7 的距离值更新为 4 和 8。
以下子图显示了顶点及其距离值，仅显示了具有有限距离值的顶点。SPT 中包含的顶点以绿色显示。
第2步：
- 选择距离值最小且尚未包含在 SPT 中（不在 sptSET 中）的顶点。顶点 1 被拾取并添加到 sptSet。
- 所以 sptSet 现在变成 {0, 1}。更新相邻顶点的距离值为 1。
- 顶点 2 的距离值变为12。
第 3 步：
- 选择距离值最小且尚未包含在 SPT 中（不在 sptSET 中）的顶点。顶点 7 被选中。所以 sptSet 现在变成{0, 1, 7}。
- 更新 7 的相邻顶点的距离值。顶点 6 和 8 的距离值更新（分别为15 和 9）。
第4步：
- 选择距离值最小且尚未包含在 SPT 中（不在 sptSET 中）的顶点。顶点 6 被选中。所以 sptSet 现在变成{0, 1, 7, 6}。
- 更新相邻顶点6的距离值。更新顶点5和8的距离值。
不断重复上述步骤直到所有的节点都被添加到sptSet集合里面去，最后，我们得到以下最短路径树（SPT）。
笔记：
- 代码计算最短距离但不计算路径信息。创建一个父数组，在距离更新时更新父数组（类似Prim最小生成树算法），并用它来显示从源到不同顶点的最短路径。
- Dijkstra's Algorithm 可用于有向图和无向图。
- 该代码找到从源到所有顶点的最短距离。如果我们仅在从源到单个目标的最短距离中感兴趣，请在挑选的最小距离顶点等于目标时停止循环。
- 实现的时间复杂度是O(V 2 )。调整后应用有限序列的做法可以将复杂度优化到 O(E * log V)
- Dijkstra's Algorithm不适用于具有负权重循环的图。对于带有负边的图，它可能会给出正确的结果，但是您必须允许一个顶点可以被多次访问，并且该版本将失去其快速的时间复杂度。对于具有负权边和环的图，可以使用Bellman-Ford ，我们会将其作为单独的帖子进行讨论。
完整代码实现下载链接：
（包含各种语言：C语言、Python、Java、C++、C#、Javascript等均有示例）文章来源：https://www.toymoban.com/news/detail-412686.html
免费资源下载：Dijkstra's Algorithm文章来源地址https://www.toymoban.com/news/detail-412686.html
到了这里，关于最短路径算法｜Dijkstra‘s Algorithm的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
