图—最短路径 Dijkstra, SPFA, Floyd

最短路径一看到最,职业病一般的就会想到用动态规划来做。。。至少事实证明的确存在动态规划的解法,但就像上一篇文章中分析的那样,这是一个具有最优子结构的问题,所以我们可以用优雅的贪心算法来解决。

这里我们用来做测试的图如下图所示,还是相当给力了

最短路径

最短路径要解决的实际问题,其实通过名字你就能看出来,从某一点出发到各个点的最短距离,我们在居家旅行,出门在外的必备算法,只不过平常我等屌丝要出去的地方不超过5个,所以从未涉及到这么高大上的算法。总共有三个算法Dijkstra, SPFA, Floyd 我们来依依介绍。

Dijkstra

Dijkstra算法是单源最短路劲算法,单源就是指定出发点,求出发点到各个点的最短距离,时间复杂度是O(n^2)。Prim算法非常相似,都是通过点来作文章,实际上如果一幅图没有环的话,Dijskta最后形成的最短路径形成的图和Prim对应的最小生成树是一致的,但是如果有环那就不一定了,例如下面的例子<s,a,5>,<a,t,5>,<s,t,9>形成一个环,s到t的距离,在最短路劲计算的时候是9,但是在最小生成树的时候是10,所以二者并不能直接划等号。

另外虽然Dijkstra 最后只需要产生 一个 dis[] 数组就可以了,但是我们仍然可以来构建一个图R来存储这些路径,为了复习和比对我们将二者的算法流程进行比对

Dijkstra Prime
0. 设置cur 为源点Sorce 0. 设置任意一个点 cur 加入到R 中
1. 更新G中与cur相邻且未被访问的点的到Source的距离,如果发生更新,记录cur到这些点对应的PRE数组的位置,例如 PRE[i] = cur 1. 更新G中与cur相邻且未被访问的点 到R的距离,如果发生了更新,记录cur到这些点对应的PRE数组的位置,例如 PRE[i] = cur
2. 选取更新后距离最短的点min,加入到R中,并且增加边 <min, PRE[min]> 2. 选取更新后距离最短的点min,加入到R中,并且增加边 <min, PRE[min]>
3. cur = min ,回到步骤1 3. cur = min ,回到步骤1

结果发现除了第二部更新的内容时候的策略不一样外,其他全都一样,也就可以发现,如果不行成环的话,未加入点的距离一定是由相邻的点更新的,二者最后产生的R是相同的。

另外第二步中 如果一点已经加入R中,说明source 到 该点距离比 到 cur距离要短,所以不可能出现,经过cur到这一点的距离,比当前该点距离短的情况。

相似的算法流程说明他们也有相似的问题,就是在处理两点之前多条路径的时候,Dijsktra 需要每次选取较小的边进行更新,这点需要注意,例如 Google RoundC Mentro刚开始死活不对,后来才发现这种情况。

SFPA

SFPA(Shortest Path Faster Algorithm), 是我在做Mentro这道题时看到大神们用的单源路径算法,当然人家敢叫fast是因为他的时间复杂度是O(kE)。(k<<V)(V 和E 分别表示点和边的数量),是基于Bellman-Ford的改进算法,1994年中国小伙儿发表的在西安交通大学学报上,简直内牛满面,中国人原创算法竟然是这样的朴素,唉被学术论文虐成渣的我就不说啥了。

他的想法也是很直观,从源点出发,更新邻居结点,如果 dis[i]的距离发生了更新,那他的邻居肯定也需要更新结点啊,那就保证dis发生改变的点压入队列之中,等他弹出之后更新邻居的点,真的很直观,而且是标准贪心,看到这么直观而简单的算法,我真的是非常的佩服啊,也很纳闷儿之前的人为啥没想到。

废话不多说,开始描述算法流程:
0. 初始化 邻接表图,int[] dis, 队列q,souce 处理之后压入q
1. 弹出队首元素cur
2. 遍历所有与cur相邻的点i,如果cur引起dis[i] 更新,且不在队列中,压入队列
3. 如果q不为空,回到步骤1。

我觉的核心步骤就是步骤2,快而简单的方法,很有实用价值,再也不用担心最短路径的问题。

Floyd

既然都有了SPFA这么好的算法,为什么也要讲这个时间复杂度为三次方给的算法呢。原因是这样的,虽然在这种场景下动态规划的算法并不是最好的,但是他并不是贪心算法,能保证全局最优解,另外Floyd的状态转移方程式非常的有代表性,压缩了状态转移矩阵,在很多动规的题目中很重要,例如背包算法的压缩。可以说我们讲这个算法不是为了他的最短路径的用处,更是为了理解动态规划的状态压缩。

Floyd 的算法流程很简单,如下:

[sourcecode language=”java”]
for(k=0;k<g.count;k++)
{
for(i=0;i<g.count;i++){
for(j=0;j<g.count;j++){
if(i==j) continue;
if(Dis[i][j] > Dis[i][k]+Dis[k][j])
{
Dis[i][j] = Dis[i][k]+Dis[k][j];
}
}}
}
[/sourcecode]

三层循环的动态规划方程,我最开始理解为,要以每个点k为中间点,求一遍跳转的之后的更新距离。。。后来发现 图样图森破,其实状态的表示 不是 Dis[i][j] 而是 Dis[i][j][k] 表示 从 i 到 j 通过 (1…k)k个元素的跳转的最短距离,参照维基百科上的说明,其状态转移方程是:

1. 如果 i 到 j 的最短路径经过k

Dis[i][j][k] = Dis[i][k][k] + Dis[k][j][k-1]

2. 如果 i 到 j 的最短路径不经过k

Dis[i][j][k] = Dis[i][j][k-1]

这是实际上是一个技巧,否则我们就要用三维的数组了,动态规划更新矩阵的时候,每次面对的实际上都是k-1的距离矩阵,在更新 Dis[i][j] 时候 Dis[i][k] 和 Dis[k][j]肯定都是之前k-1时对应的数值,因为在 更新 Dis[i][k] 直接意义上讲通过(1….k-1)和(1….k)到k的距离是一样的,并不会因为多加一个他本身就改变。
而公式方面 Dis[i][k] = Dis[i][k]+Dis[k][k] 后者为0,因此在k是 Dis[i][k] 保持不变,同理Dis[j][k] 也会保持不变,因此可以压缩数据。

参考资料:
Floyd算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.