最短路径 | 深入浅出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),这里我们可以用 优先队列(堆) 来优化,使得这一部分的时间复杂度降低到 。这个我们将在后面讨论。