今天学了个最简单的最短路算法
真的超简单的......
用邻接矩阵存图,然后开始我们的蒂花之秀~~~
Floyd --
运用动态规划的思想,枚举每个点的最短路径
状态转移方程： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的点(意思就是从i->k->j的距离)
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路,一般赋值为0x3f3f3f3f。
处理代码:
void Floyd(){
for(int k=0;k<len;k++)
for(int i=0;i<len;i++)
for(int j=0;j<len;j++)
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}对,就是个很暴力的三重循环,处理完后,任意map[i][j]都代表从i->j的最短路径
需要注意的是这个算法时间复杂度很高O(n^3),很可能会超时....
但是真的很简单啊.....~~~~~
不会的甚至可以直接背下来
还有两点需要注意的是:
k必须放在外面,不然可能遍历不完全i,j随意
floyd不能处理负权图!!!!
具体为什么等我搞明白了再写~~
大佬们可以参考知乎回答https://www.zhihu.com/question/30955032