最短路径问题
最短路径问题分为两大类,单源最短路径,和多源汇最短路径,一般主要考察第一种,第二种书上一般只介绍floyd算法。
单源最短路径
- dijkstra (边权均为正数)
- Bellman-ford (可以处理负权边的情况)
- spfa (优化版,更新过的入队列)
Dijkstra
Dijkstra是用来求非负权值的单源最短路径,问题是:给定一个n个顶点有向图,边权均为正值,求从1号点到其他各顶点的最短路径。
算法步骤
1、数组dist[N]存储1号点到其他所有点的距离,dist[1] = 0,其他为无穷。
2、n次循环 每次 (1. 找不在集合s中距离最近的点,记为t, t加入集合s。2. 用t更新其他点距离(松弛操作))
s为已经确定最短距离的点,松弛操作为用t到1号点的距离+t到待更新点j的距离更新j到1号点的距离。
1 | dist[j] = min(dist[j],dist[t] + w); //w为t到j的距离 |
由以上步骤可以推出dijkstra算法复杂度为O(n^2), 主要花费在每次需要找最小距离的点,这一操作为O(n)。
代码如下
1 |
|
堆优化版
上述Dijkstra算法最耗时的部分在于每次找最大值,与点的个数的平方成正比,如果图中点数很多而边数很少(稀疏图),那么算法复杂度会很高。考虑用堆存储不在s中的点的距离,这样每次找最小距离的复杂度减为O(1),同时在松弛操作时每次更新dist操作的复杂度为mlogn。在利用邻接表存储时,松弛操作实际只执行了m次。
代码如下
1 |
|
Bellman-ford
有负权边的时候,dijkstra算法无法求解出最短路径。Bellman-ford算法的思路是依次迭代求解出经过不超过k条边的最短距离。算法步骤为
1 | 循环k次 |
算法不能处理包含负权回路的情况,因为包含了负权回路的话,最短距离会不断更新直到负无穷。
代码如下
1 |
|
spfa
spfa算法是Bellman-ford的一个优化版,在松弛的时候,只把更新之前有变化的dist,将dist改变的放入队列,对队列中的点更新出边。
1 | int spfa(){ |
spfa算法可以用来判断负环,在上面的算法中维护一个cnt数组,每次更新的时候对应的cnt++,表示当前最短距离经过了cnt[i]条边,如果cnt[i] >= n表示至少经过了n+1个点,所以至少有两个点相同,也就是路径上存在回路。
floyd算法
floyd算法求解的是所有顶点的最短路径,给出任意两个点,求出他们之间的最短距离。算法步骤比较简单,三次循环,松弛。
1 | void floyd(){ |
算法初始时以任意两个顶点之间的有向边作为路径长度,然后不断在路径中加入中间顶点来更新。d[i] [j]表示i到j的最短距离经过1-k的点。
最小生成树
生成树是连通图的一个极大无环子图,总边权值最小的生成树为最小生成树。
构建最小生成树的算法有prim和kruskal算法
Prim
算法思想,将顶点集合分为两部分,一部分在最小生成树中,一部分不在,每次将距离生成树集合最近的点加入即点到生成如集合内所有点最短的那条边(桥)(可用堆优化),再用该点更新其他点到生成树集合的最短距离。用于稠密图
算法步骤:
1 | dist数组存储每个点到生成树集合的距离:初始化为INF |
代码:
1 |
|
kruskal
算法思想:每次选最短的边,如果两端点不在同一联通分量中,则加入生成树,并合并集合。适用于稀疏图
1 |
|
两种算法都使用了贪心思想。