图之单源最短路径 Bellman-Ford算法 Dijkstra算法 SPFA算法

忘是亡心i 2021-09-11 01:36 376阅读 0赞

## **一.实际问题** ##

![这里写图片描述][20160831184025435]  
一般情况下广度优先搜索能够解出单位权值问题，只需要进行广度搜索，最先到达目的地的路径最短。但是对于非单位权值就没有办法，不同于单位权值每天边的代价相等，非单位权值每条边代价不等。这样我们就不能每次往下一次搜索时前面各条路径代价相同。如果非要采用广度搜索那只能把每条能够到达目的地的路径的总代价都计算出来，取最小值。

## **二.一些定义** ##

![这里写图片描述][20160831185047198]  
显然，如果从Vi到Vj有更短的路径，那为何不使用这条最短路径使路径代价更短，但是这与我们假设相悖。  
![这里写图片描述][20160831185746675]  
如果存在负回路的话，那我们就可以一直走这条负回路使代价最后趋于负无穷。  
![这里写图片描述][20160831192008579]  
松弛技术主要用于当我们发现更短路径时，要用这个更短路径替换当前比较大的路径，同时要对其他路径进行代价更新。

## **三.Bellman-Ford算法** ##

> 可用于存在负权值边情况。算法使用松弛技术，逐步减小从S到V的最短路径总权值估计值，直到得到最短路径。

![这里写图片描述][20160831195612609]  
![这里写图片描述][20160831200611019]  
观察算法以及示意图，我们知道：Ford算法在每次循环时候把所有的边都试探性的尝试松弛，如果满足要求的话就进行松弛。  
a\}中初始假设所有从s到的节点的路径都为无穷大。  
b)在第一次循化，其他的都是无穷大加上一个数还是无穷大，只有S-t，S-y是0加上6或7，小于无穷大，进行松弛。  
c)第二次松弛同理，经过尝试所有边后，只有6+(-4)=2,7+(-3)=4小于无穷大，可以进行松弛。  
d)在第三次循环，可以发现在尝试x-t边是4+(-2)=2<6（先前s-t路径），代价更小，进行松弛，抛弃原有的6  
最终在经过n-1松弛后达到最短路径。

**关于源点可达负回路问题：假设从t-x为5，从x-t为-8。则x-t之间是负回路，且源点可达。那么：我们在上述循环d)中会发现4+(-8)=-4<6（t顶点），再进行下一次循环-4+5=1<4，再进行下一次循环1+(-8)=-7<-4…….如此，我们发现每次循环t和x节点的代价都会减小，如果可以循环无数次的话最终到达负无穷。所以红色方框内对源点可达负回路进行验证，如果存在负回路，问题无解，返回False。**

> 检验原理：d\[v\]和d\[u\]如果没有存在源点可达负回路情况下循环完成后已经是最短路径了，但是如果存在负回路，在红色方框中我们就会发现d\[v\]>d\[u\]+w(u,v)，也就是我们找到了另一条更短的从u到v路径。但这是不可能发生的，除非出现负回路。

[SPFA算法图解，非常好的一篇文章，内容也可看本文末尾截图][SPFA]

## **四.Dijkstra算法** ##

> Dijkstra算法采用贪心策略，每次都选择代价最小的路径加入到它的顶点集中。要求边非负。

![这里写图片描述][20160831205221299]  
红色方框中黑点是每次贪心选择的顶点。  
Dijkstra算法思想在于每次选择距离顶点集最小的路径的顶点。  
1、在初始化时如果s能够直达某个顶点则初始时赋直达路径代价，如果不能赋无穷大。默认s已在顶点集中。可以看到y，t被赋值5，10，其他无穷大。  
2、图c中第一次循环选择s-y。**为啥？s的出度有两个s-t（10）和s-y（5）。显然达到顶点y有两种方式：s-y（代价5）或s-t-…-y（代价10+…..），5<10，选s-y一定是s到y的最短路径。**  
3、然后我们把顶点y加入节点集，同时更新其他路径，如果其他路径走（s-y-其他）比（s直达其他）代价更小，则替换成新的路径。更新如下：t：10-8；x：无穷-14；z：无穷-7。也就是把第一种从s走其他节点的方法部分替换为从s走y走其他节点方法。  
4、在图c)中，节点集到t，x，z有四种方式，这是我们又选择顶点z，同理，从s到z比s到t，x代价小，那么从s到z就不会经过t和x，不考虑后续是否还经过其他顶点情况下，s到t，x比s到z就已经代价大了。  
如此反复。  
伪代码：

// 初始化，赋值直达或无穷大
    for i=[0,n)
        dist[i] = tab[0][i]
    visit[0] = true;
    
    for i=[1,n)
        min = MAX_VALUE
        // 遍历寻找从s到j的最小路径节点，因为该节点除了找到的路径无论从其他那个路径都要比已找到的代价大。
        for j=[0,n)
            if !visit[j] && dist[j]<min
                min = dist[j]
        // 将该点加入已访问集
        visit[j] = true
    
        // 由于在加入j之前节点集中所有节点到非节点集节点的路径都已更新，现在考虑是否有路径通过绕路过j节点获得更小路径。也就是松弛边(j,v)，其中中v为非节点集顶点。
        for k=[0,n)
            if !visit[k] && dist[k]>dist[j]+tab[j][k]
                dist[k] = dist[j]+tab[j][k]

[算法实例：CCF 交通规划][CCF]

## **五.SPFA算法** ##

SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。在这对别人文章截个图，担心以后删除找不到啥的。感觉SPFA就是广搜，一直搜索直到搜索到最小路径，这时就无法找到比它更小路径，从而结束当前点的松弛。当到节点的最短路径更新时，说明以当前节点为前序点的节点最短路径信息都得更新，不过每次只更新后续路径的一个节点后就判断是否压栈，从而避免一直考虑更新该路径。  
[CCF 无限网络][CCF 1]  
![这里写图片描述][SouthEast]

[20160831184025435]: /images/20210520/894f28ef7afb4c3d895753350077b3a1.png
[20160831185047198]: /images/20210520/569ee05a99e7491d9b48d41915e56cbf.png
[20160831185746675]: /images/20210520/165eab23a9c843b8b6b73eebcd8b475f.png
[20160831192008579]: /images/20210520/f79f1ffd920841748ef0784143fbc81d.png
[20160831195612609]: /images/20210520/9c315e664b5e4a5d8d1c1defadf53420.png
[20160831200611019]: /images/20210520/1068400e7bc54ec29a9b6552a1c83794.png
[SPFA]: http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml
[20160831205221299]: /images/20210520/2ca2291f97c5425984aa748081e84a17.png
[CCF]: http://blog.csdn.net/qq_16234613/article/details/77347785
[CCF 1]: http://blog.csdn.net/qq_16234613/article/details/77482417
[SouthEast]: /images/20210520/61514f450d614b1d9151200c78c04fe9.png