最短路算法(dijkstra,bellman_ford,floyd)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了最短路算法(dijkstra,bellman_ford,floyd),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1410字,纯文字阅读大概需要3分钟。
内容图文
最短路算法
dijkstra(初级的最短路算法,适合稠密图,可用邻接表优化)
bool relax(int u,int v) { double tmp=max(dist[u],edge[u][v]); if(tmp<dist[v]){ dist[v]=tmp; } } void dijkstra() { memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++){ int x; double mindist=INF; for(int j=0;j<n;j++){ if(vis[j]) continue; if(dist[j]<mindist) mindist=dist[x=j]; } vis[x]=1; for(int v=0;v<n;v++){ if(v==x) continue; relax(x,v); } } }
bellman_ford(实用高效的最短路算法,实际复杂度远小于最坏复杂度o(NM),可判断负环)
bool bellman_ford() //bool 判断是否有负环{ for(int i=0;i<n;i++) dist[i]=(i==s)0:INF; for(int i=0;i<n-1;i++){ //松弛n-1次,实际小于n-1次bool flag=0; //此变量判断能否继续松弛,若不能退出算法for(int j=0;j<e;j++){ if(relax(j)) flag=1; } if(dist[s]<0) returntrue; if(!flag) returnfalse; } for(int i=0;i<e;i++){ //此处检查负环,如果松弛了n-1次还能继续松弛说明有负环if(relax(i)) returntrue; } returnfalse; }
int bellman_ford() { for(int i=0;i<n;i++) dist[i]=(i==s)0:INF; for(int i=0;i<n-1;i++){ bool flag=0; for(int j=0;j<e;j++){ if(relax(j)) flag=1; } if(!flag) break; } return dist[s]; }
floyd(适合求任意两点的最短路或传递闭包判断拓扑序列,时间复杂度较高)
void floyd() { for(int k=1;k<=n;k++){ for(int u=1;u<=n;u++){ for(int v=1;v<=n;v++){ if(edge[u][v]<edge[u][k]+edge[k][v]) edge[u][v]=edge[u][k]+edge[k][v]; } } } } /* 传递闭包:将循环内改成这样即可: if(G[u][k]&&G[k][v]) G[u][v]=1; */
除此之外求最短路还有SPFA,A*等算法,以后再慢慢学------
原文:http://www.cnblogs.com/--560/p/4329978.html
内容总结
以上是互联网集市为您收集整理的最短路算法(dijkstra,bellman_ford,floyd)全部内容,希望文章能够帮你解决最短路算法(dijkstra,bellman_ford,floyd)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。