floyed O(n^3)
f[i][j] = min(f[i][j] ,f[i][k] + f[k][j] )
memset(f,inf,sizeof(f)); for(i=1;i<=m;i++) cin>>x>>y>>z,f[x][y]=f[y][x]=z; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(i==j) f[i][j]=0; else if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j]; }
Dijkstra (只能处理正权图
该算法用 d[i] 保存起点到其他点的距离,初始为无穷
每次找d[i] 最小的点i ,以此更新 d[y] = min(d[y], d[i]+ len(i,y) )
找最小的 d[i] 可以用优先队列优化一下
#include <iostream> #include <cstring> #include <queue> using namespace std ; struct T{ int y,z; T(int y0,int z0){ y=y0,z=z0; } bool operator<(T a)const{ return z>a.z; } }; const int N=1e4+1,M=1e6+1,inf=0x3f3f3f3f; int n,b[N],d[N],nxt[M],w[M],go[M],hd[N],all; void add(int x,int y,int z){ go[++all]=y,nxt[all]=hd[x]; hd[x]=all,w[all]=z; } priority_queue<T> q; void dijk(int v0){ int i,x,y,z; memset(d,inf,sizeof d); d[v0]=0; q.push(T(v0,0)); while(q.empty()==0){ x=q.top().y,q.pop(); if(b[x]) continue; b[x]=1; for(i=hd[x];i;i=nxt[i]){ y=go[i],z=w[i]; if(d[x]+z<d[y]){ d[y]=d[x]+z; q.push(T(y,d[y])); } } } } signed main(){ int v0,i,x,y,z,m; std::cin>>n>>m>>v0; for(i=1;i<=m;i++) cin>>x>>y>>z,add(x,y,z); dijk(v0); for(i=1;i<=n;i++) cout<<d[i]<<' '; }
SPFA 边权可负
int all,nxt[M],go[M],hd[N],vis[N],w[M]; int dis[N],n,m; void add(int x,int y,int z){ go[++all]=y; w[all]=z,nxt[all]=hd[x],hd[x]=all; } queue<int> q; void spfa(int v0){ int i,x,y,z; for(i=0;i<=n+1;i++) dis[i]=inf; dis[v0]=0; q.push(v0); while(!q.empty()){ x=q.front(),q.pop(); vis[x]=0; for(i=hd[x];i;i=nxt[i]){ y=go[i],z=w[i]; if(dis[y]>dis[x]+z){ dis[y]=dis[x]+z; if(!vis[y]) vis[y]=1,q.push(y); } } } }
原文地址:http://www.cnblogs.com/towboa/p/16880172.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性