最短路径
2022/2/10 23:20:45
本文主要是介绍最短路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
floyd
是一种动态规划算法,稠密图效果最佳,边权可正可负
他的原理在于用邻接矩阵存任意两点之间的最短路径,适用于多源最短路,点与点之间:
- 自己到自己——dis=0;
- 自己到别人——找一mid,随机二分,就一区间DP
//k为中间点 for(k = 0; k < G.vexnum; k++) //v为起点 for(v = 0 ; v < G.vexnum; v++) //w为终点 for(w =0; w < G.vexnum; w++) if(D[v][w] > (D[v][k] + D[k][w])) { D[v][w] = D[v][k] + D[k][w];//更新最小路径 P[v][w] = P[v][k];//更新最小路径中间顶点 }
dijkstra算法
#include<bits/stdc++.h> #define MAXN 100010 #define INF 2147483647 #define ll long long using namespace std; struct edge{ll w,v;}; ll n,i,j,beg,end,x,y,z,m; vector<edge> g[MAXN]; edge E,E1; ll dis[MAXN],vis[MAXN]; struct Node{ ll w,v; bool operator < (const Node& x) const{ return v>=x.v; } }; priority_queue<Node> q; Node node; namespace Fastio{ inline ll read(){ ll x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-48;c=getchar();} return x; } void write(ll x){ if(x/10>0) write(x/10); putchar(x%10+48); return; } } using namespace Fastio; inline void Dijkstra(){ while(!q.empty()){ ll ww=q.top().w;q.pop(); //取出队列首元素,队列放出元素 if(vis[ww]) continue; //如果访问过此节点,直接continue vis[ww]=1; //将该节点设置为走过 for(i=0;i<g[ww].size();i++){ ll w=g[ww][i].w; //取出与该点所有相连的点 ll v=g[ww][i].v; //取出与该点相连的点的边权值 if(v+dis[ww]<dis[w]){ //如果比当前节点所用过的最短路径要小 dis[w]=dis[ww]+v; //更新最小值 node.w=w;node.v=dis[w]; q.push(node); //扔进堆里 } } } } int main(){ n=read();m=read();beg=read() for(i=1;i<=m;i++){ x=read();y=read();z=read(); E.w=y;E.v=z; g[x].push_back(E); // 将这点x的下一个点设成y,权值为z,放进vector中。注意是有向图...我不会告诉你我以为是无向图而WA了n次= = } for(i=1;i<=n;i++) dis[i]=INF; //注意,如果偷懒的话必须要写一个for循环,使用memset会出问题 dis[beg]=0; node.w=beg;node.v=0; q.push(node); Dijkstra(); for(i=1;i<=n;i++){write(dis[i]);putchar(' ');} }
贪心,有负权不行:a->b=5,c->b=-2,a->c=6;最短路是6-2=4,但Dij会算成5
这篇关于最短路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙