图论 *最短路*
2022/2/16 23:12:23
本文主要是介绍图论 *最短路*,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
多源最短路:Floyd
所谓多源,就是求图中任意两点的最短路。
floyd是一种动态规划的做法。
首先我们给出状态定义:$f(i,j,k)$ 表示除了点$i j$外,只经过$1~k$个点, $i$到$j$的最短路,不难得出状态转移方程:$ f(i,j,k) = min(f(i,k,k-1)+f(k,j,k-1)) $
优化掉$k$那一维之后就变成 : $f(i,j) = min(f(i,k) + f(k,j))$ 。该算法处理图的边权,可正可负,复杂度 $O(n^3)$。
for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) f[i][j] = min(f[i][j],f[i][k] + f[k][j]); //初始化f[i][j]即为两点边权,否则为正无穷
单源最短路
就是求从给定点到其余点的最短路
Dijkstra
该算法需要一个$dis$数组,$dis[u]$代表从点$u$到起点的最短路。
初始时,起点dis值为0,其余都为正无穷。
每次取出dis最小的点并删除,遍历他的所有出边进行松弛操作,直至全部结束。
取dis的过程可以用堆,也就是STL里的priority_queue来实现,总复杂度$O(nlog(n+m))$ 。
松弛操作:对于一个点v和一个点u,若dis[v] > dis[u] + w[u][v] 则dis[v]更新为dis[u] + w[u][v] ,可以形象的想象一个图,原来的dis中点v从原点x过来经过一条路径,现在变为从x到u再到v,路径更短,但看起来像绳子更松的样子,这也是为什么叫作松弛操作。
PS:Dijkstra只能用在非负权图,负权图得SPFA!!!
struct qwq{ int u,dis; bool operator <(qwq a)const{return dis > a,dis;}//STL默认大根堆,这样改成小根堆,也就是先出小的 }; inline void dijkstra(){ memset(dis,0x3f3f3f3f,sizeof(dis)); priority_queue<qwq> q; dis[start] = 0; q.push((qwq){start,0}); while(!q.empty()){ int u.q.top();q.pop(); if(vis[u])continue; vis[u] = 1; for(int i=head[u];i;i=nxt[i]){ int v = to[i]; if(dis[v] > dis[u] + w[i]){ dis[v] = dis[u] + w[i]; q.push((qwq){dis[v],v}); } } } }
SPFA
首先关于这个算法有一句话不得不说——————————它 !死 !了 !
但是呢,又没完全死,因为在构造数据下它太容易被卡掉,但是有的时候我们写不出正解,所以它反而又是我们不得不用的。
首先他的复杂度,点数为N,边数为M, 期望复杂度$O(M) $ 但最坏复杂度$O(NM)$ 所以能用dijkstra 就别用SPFA 反复鞭尸
我们同样维护一个$dis$ ,只不过这回用队列来实现。
首先放入起点
每次取出队首元素,访问所有出边,进行松弛操作,如果连接的点没有入过队,将它入队。
直到队空
inline void spfa(){ memset(dis,0x3f3f3f3f,sizeof(dis)); dis[start] = 0; vis[start] = 1; queue<int>q; q.push(start); while(!q.empty()){ int u = q.front();q.pop(); for(int i=head[u];i;i=nxt[i]){ int v = to[i]; if(dis[v] > dis[u] + w[i]){ dis[v] = dis[u] + w[i]; if(!vis[v])q.push(v),vis[v] = 1; } } } }
这篇关于图论 *最短路*的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?