单源最短路径问题
Dijkstra算法
过程:在图中找距离源点最短路径的点,随后用这个最短路径的点去更新与之联通的点。
邻接矩阵版
1 | int G[maxn][maxn]//G是邻接矩阵,存储的是两点之间的距离,无穷大表示不可达 |
邻接表版
邻接表版与他只有在后面更新结点的方式有所不同,由于在邻接表中所存储的每一个点都是有效点,所以可以省去G[u][a]<INF的判断
1 | struct node |
bellman-fold算法
bellman-fold算法相比djkstra算法的优势就是他能处理负权边,同时也能判断图中是否存在负环,当执行次数大于n-1时,图中最短路仍然在更新,说明一定存在负环。
过程:遍历所有的边,判断该条边是否能让与之相邻的点的距离最小,能就更新,将这个过程执行n-1次。
我们选择用遍历点的方式来遍历与之相连的所有的边,所以在这里就涉及到了三重循环,所以并不建议使用邻接矩阵,建议使用邻接表
1 | const int maxn=510,INF=0x3fffffff; |
SPFA算法
SPFA算法时bellman-fold算法的升级版本,其特点是用一个队列保存已经更新过的结点(边),用于更新下一个,这样就省去了不必要的循环操作。
1 | const int N=510,INF=0x3fffffff; |
全源最短路径问题
Floyd算法
过程:在所有点里面找一个中介点,并尝试用这个中介点去更新所有与之相连的所有的点
1 | void Floyd(int st) |
找出最短路径
最短路径的存储方式我们可以通过一个二维数组存下他的上一个结点比如 1->2->3->4
即为:pre[4]=3,pre[3]=2,pre[2]=1,pre[1]=1;
这种存储方式的优点是可以存下多个不同的最优路径
例如1->3->4,1->2->4
即为:pre[4]={2,3},pre[3]={1},pre[2]={1},pre[1]={1};
1 | if(d[v]>d[u]+G[u][i].dis) |
使用递归就能很简单的列出所有路径的。
最短路径的条数
1 | num[st]=1; |
上述方法只能用于dijkstra算法中,由于在bellman-fold和SPFA算法中会重复遍历结点,导致路径数目重复计算,所以会失效。
在这里利用set不会重复的特性来存储路径
以SPFA为例
1 | if(d[v]>d[u]+G[u][i].dis) |
多个最短路径的选择问题(第二标尺)
现在以路径最短为第一标尺记为d,花费最少为第二标尺,记为w,weight是每个点的花费
1 | if(d[v]>d[u]+G[u][i].dis) |
当标尺过多时,编写的条件逻辑会很复杂,而且容易出错,我们可以先求出第一标尺的最优路径,用pre记下,然后用DFS专注于剩下的标尺的求解。
例如Dijkstra+DFS
PAT1030
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/07/08/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!