引言

在计算机科学和图论中，算法在有效解决复杂问题方面起着至关重要的作用。其中一个突出的算法是Dijkstra算法，它由荷兰计算机科学家Edsger W. Dijkstra于1956年开发。Dijkstra算法已经成为路途导航和网络优化领域的基石。

Dijkstra算法

Dijkstra算法是一种常用的算法，用于查找加权图中两个节点之间的最短路径。它基于贪婪原理，每一步中总是选择具有最小暂定距离的节点。这样可以保证算法首先探索一条最有希望的路径，从而找到最短路径。

算法步骤

1. 初始化：为图中的每个节点分配一个暂定的距离值。将源节点的距离设置为0，所有其他节点的距离设置为无穷大。将所有节点标记为未访问。
2. 选择最小距离节点：从所有未访问节点中选择具有最小暂定距离的节点作为当前节点。
3. 相邻节点的探索：遍历当前节点的所有相邻节点。
4. 更新距离：对于每个相邻节点，如果从源节点到该节点的路径长度（通过当前节点）小于其当前暂定距离，则更新该相邻节点的暂定距离。
5. 标记为已访问：将当前节点标记为已访问。
6. 选择下一个当前节点：重复步骤2-5，直到所有节点都被标记为已访问。
7. 最短路径重构：根据暂定距离值，重构从源节点到所有其他节点的最短路径。

重要限制

需要注意的是，Dijkstra算法假设边的权重不是负值。边的权重为负可能使算法产生误报或使其进入无限循环。如果边的权重为负，应该使用Bellman-Ford算法或A算法等其他算法。

效率和最优性

效率

Dijkstra算法的时间复杂度为O((V+E)logV)，其中V表示图中节点的数量，E表示图中的边数。为了提高算法的性能，可以使用有效的数据结构，例如优先级队列或最小堆。

最优性

在边的权重非负的情况下，Dijkstra算法保证找到图中源节点与所有其他节点之间的最短路径。这是因为贪婪原理保证算法始终选择最短的路径。

现实世界的应用程序

Dijkstra算法由于能够在加权图中找到最短路径，因此在现实世界中有很多应用。以下是一些最突出的应用：

导航系统

Dijkstra算法被广泛应用于导航系统中，以确定两个位置之间的最短路线。通过将道路网络表示为加权图，节点表示路口，边表示具有相关权重（如距离或旅行时间）的道路，该算法帮助驾驶员找到最有效的路径。

网络路由

在计算机网络中，路由器使用Dijkstra算法来确定传输数据包的最佳路径。通过将网络拓扑视为一个图，并根据延迟或带宽等因素为链路分配权重，该算法有助于最小化延迟和拥塞。

运输与物流

Dijkstra算法应用于运输和物流管理系统。它帮助优化递送服务、公共交通系统和航空网络的路线。通过考虑距离、交通状况或运输成本等因素，该算法有助于最大限度地减少旅行时间，减少燃料消耗，提高运输效率。

结论

Dijkstra算法是一种有效的算法，用于查找加权图中两个节点之间的最短路径。它以其效率、最优性和广泛的现实世界应用而著称。Dijkstra算法在许多领域发挥着至关重要的作用，例如导航、网络路由和运输，它将继续在解决复杂问题和优化系统中发挥关键作用。

【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法

迪杰斯特拉(Dijkstra)算法核心： 按照路径长度递增的次序产生最短路径。

迪杰斯特拉(Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路径，而是 一步一步求出它们之间顶点的最短路径 ，过过程中都是 基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径 。

弗洛伊德(Floyd)算法是一个经典的 动态规划算法 。

最短路径 | 深入浅出Dijkstra算法（一）

上次我们介绍了神奇的只有 五行的 Floyd-Warshall 最短路算法 ，它可以方便的求得 任意两点的最短路径， 这称为 “多源最短路”。

这次来介绍 指定一个点（源点）到其余各个顶点的最短路径， 也叫做 “单源最短路径”。 例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。

与 Floyd-Warshall 算法一样，这里仍然 使用二维数组 e 来存储顶点之间边的关系， 初始值如下。

我们还需要用 一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程， 我们可以称 dis 数组为 “距离表”， 如下。

我们将此时 dis 数组中的值称为 最短路的“估计值”。

既然是 求 1 号顶点到其余各个顶点的最短路程， 那就 先找一个离 1 号顶点最近的顶点。

通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。 当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”， 即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。

为什么呢？你想啊， 目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。 因此 1 号顶点到其它顶点的路程肯定没有 1 号到 2 号顶点短，对吧 O(∩_∩)O~

既然选了 2 号顶点，接下来再来看 2 号顶点 有哪些 出边 呢。有 2->3 和 2->4 这两条边。

先讨论 通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。 也就是说现在来比较 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程，dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，e[2][3]表示 2->3 这条边。所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->3 这条边，到达 3 号顶点的路程。

我们发现 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新为 10。这个过程有个专业术语叫做 “松弛” 。即 1 号顶点到 3 号顶点的路程即 dis[3]，通过 2->3 这条边 松弛成功。 这便是 Dijkstra 算法的主要思想： 通过 “边” 来松弛 1 号顶点到其余各个顶点的路程。

同理通过 2->4（e[2][4]），可以将 dis[4]的值从 ∞ 松弛为 4（dis[4]初始为 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新为 4）。

刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为：

接下来，继续在剩下的 3、4、5 和 6 号顶点中，选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组，当前离 1 号顶点最近是 4 号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边（4->3，4->5 和 4->6）用刚才的方法进行松弛。松弛完毕之后 dis 数组为：

继续在剩下的 3、5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 3 号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边（3->5）进行松弛。松弛完毕之后 dis 数组为：

继续在剩下的 5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 5 号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后 dis 数组为：

最后对 6 号顶点的所有出边进行松弛。因为这个例子中 6 号顶点没有出边，因此不用处理。 到此，dis 数组中所有的值都已经从“估计值”变为了“确定值”。

最终 dis 数组如下，这便是 1 号顶点到其余各个顶点的最短路径。

OK，现在来总结一下刚才的算法。 Dijkstra算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

基本步骤如下：

在 博客 中看到两个比较有趣的问题，也是在学习Dijkstra时，可能会有疑问的问题。

当我们看到上面这个图的时候，凭借多年对平面几何的学习，会发现在“三角形ABC”中，满足不了 构成三角形的条件(任意两边之和大于第三边)。 纳尼，那为什么图中能那样子画？

还是“三角形ABC”，以A为起点，B为终点，如果按照平面几何的知识， “两点之间线段最短”， 那么，A到B的最短距离就应该是6(线段AB)，但是，实际上A到B的最短距离却是3+2=5。这又怎么解释？

其实，之所以会有上面的疑问，是因为 对边的权值和边的长度这两个概念的混淆， 。之所以这样画，也只是为了方便理解（每个人写草稿的方式不同，你完全可以用别的方式表示，只要便于你理解即可）。

PS：数组实现邻接表可能较难理解，可以看一下 这里

参考资料：

Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。

根据这个原理， 用Dijkstra算法求最短路径的图不能有负权边， 因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。

那么，有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法（即“单源最短路径”问题）呢？答案是有的， Bellman-Ford算法 就是一种。（我们已经知道了 Floyd-Warshall 可以解决“多源最短路”问题，也要求图的边权均为正）

通过 邻接矩阵 的Dijkstra时间复杂度是。其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用 优先队列（堆） 来优化，使得这一部分的时间复杂度降低到。这个我们将在后面讨论。