单源最短路
单源最短路的意思就是一个起点,算出到其他点的最短路,这里介绍三种算法,bellman-ford,spfa和dijkstra
BF算法
算法思想
BF是bellman_ford的简称,算法的想法非常简单,进行$|V|-1$次操作,每次操作对所有的边松弛。
松弛可以形象的理解为更新值,比如有一条从$u$到$v$的边,如果$u$上的值加上边的长度小于$v$上的值,那么就更新$v$上的值。
为什么这样做是对的呢?我们可以回顾整个过程,第一次操作,我们一定能将起点出去的点中的某一个点更新为最小值(这个点以后不会被更新),关于这点可以用反证法证明,如果没有一个点是更新完毕的,那么从起点到这个点必然存在一条比起点到这个点的边更短的路径,与假设矛盾。故而每次我们至少能确定一个点,所以总共需要$|V|-1$次(起点不用更新)。
最开始的图,0是起点
初始化
第一次松弛更新了1,2,3三个点
最后全部更新好了
算法实现
|
|
复杂度分析
复杂度很明显是$O(V*E)$,在完全图的时候,会变成$O(V^3)$
SPFA算法
SPFA算法又叫做bellman-ford队列优化,至于为啥叫SPFA我也不知道。
算法思想
纵观整个BF算法,我们可以用宽度优先搜索来代替V-1次的暴力松弛,每次用队列头部的元素去更新其他点,如果将一个点更新成功,就将这个点加入队列,直到更新不动为止。
可以证明,这样做和BF本质上是一样的。但这样做有个好处,这个好处就在于我们可以记录一个点是否在队列中,如果这个点在队列中,那么我们知道这个点一定会被拿出来松弛,那么当这个点被更新的时候,我们就不用讲他加入队列了。如此,就大大改进了BF算法。
算法实现
|
|
算法复杂度
这个算法的复杂度是个迷,据传是$O(k*E)$,其中$k$是个不大的常数。
Dijkstra算法
算法思想
我们依旧用宽度优先搜索的角度思考BF算法,我们发现,如果我们每次都将最小的值从队列中拿出,那么拿出来的一定是已经更新好了的(同样可以用反证法证明),所以只要我们将队列变成堆,就能快速处理最短路了。
还是刚刚那个图,最开始将0号节点加入堆
现在从堆中拿出最小的数0,用他更新1,2,3,并把1,2,3加入堆
现在堆里面最小的数是2号节点,说明2号节点已经更新好了,那么用2号节点去更新其他节点
最好都更新好了
算法实现
|
|
算法复杂度
由于我们至少将所有边遍历一次,所以我们需要$O(E)$的时间,堆优化使得我们在搜索时将一个$V$的复杂度降到$logV$,所以时间复杂度为$O(E+VlogV)$
多源最短路
如果我们想知道任意两个点之间的最短路,这时候可以暴力跑n次单源最短路,也可以用floyd算法
Floyd算法
这个算法的特点就是非常好写
算法思想
Floyd算法运用了动态规划的思想,对于一个最短路径(u,v)而言,我们一定是从u到了k,再从k到v。所以我们只要知道了(u,k)和(k,v)的最短路,那么我们就能得到(u,v)的最短路。
所以暴力枚举就好
算法实现
|
|
算法复杂度
很明显,复杂度是$O(V^3)$