最短路径算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最短路径算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1333字，纯文字阅读大概需要2分钟。

内容图文

弗洛伊德算法(Floyed-Warshall)

适用范围及时间复杂度

该算法的时间复杂度为O（N^3），适用于出现负边权的情况。

可以求取最短路径或判断路径是否连通。可用于求最小环，比较两点之间的大小。

（什么？？你不知道什么是负边权？？戳->http://t.cn/Ef7pbu6）

核心思想

对于任意一个K点，i到j的距离有两种可能：要么经过k点，要么不经过k点。所以我们只需要不断的迭代k，比较d[i][k]与d[i][k]+d[k][j]的值。如果后者更短，则更新d[i][k]的值。如此重复，最后检查完所有的k时，我们便得到了最短距离。

注意事项及常见问题

由核心思想不难看出，这个算法需要三层循环来实现。但k的位置是值得注意的。经过分析不难发现，k属于最外层循环。

i,j,k三点并不能相同。如若相同，则算法无意义。（自己到自己的距离当然是零啦）

在使用算法时，将map[i][j]值初始为最大/小，map[i][i]一定设置为0（自己到自己当然是零啦）

有时题目会暗含重复数据，也就是相同的路径权重不同。所以要根据题目进行数据比较，更新最大/小的值。

代码实现

初始化：如若两点（假定两点为u,v）相连，则其最短路径初始化为权重。如不相连则初始化为巨大值（0x7ffffff）

1 if(w[u][v]){
2     dis[u][v]=w[u][v];
3 }else{
4     dis[u][v]=0*7ffffff;                 
5 }

戳开查看

step2:寻找中间点K，比较距离并判断是否更新。

1 for(int k=1;k<=n;k++){
2     for(int i=1;i<=n;i++){
3         for(int j=1;j<=n;j++){
4             if(i!=k&&i!=j&&j!=k){
5                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
6             }
7         }
8     }
9 }

戳开查看

 

内容总结

以上是互联网集市为您收集整理的最短路径算法全部内容，希望文章能够帮你解决最短路径算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---