图论最短路径之Floyd算法
Floyd算法主要思想
我们在求任意两点间的最短路径时，可以循环一遍所有点，轮流作为源点，然后用dijkstra或bellman算法求解，时间复杂度是O(n3)，也可直接使用Floyd算法，更直接，时间复杂度也为O(n3)。
Floyd的代码很简单，其核心代码只有5行：
for(int k = 1;k <= n;k++) //循环1-n所有顶点for(int j = 1;j <= n;j++) //循环终点for(int i = 1;i <= n;i++) //循环起点if(e[i][j] > e[i][k] + e[k][j])e[i][j] = e[i][k] + e[k][j];
最外层我们循环n个顶点，判断借助该点是否能更近的从i点到j点，i和j我们依次循环所有顶点。这样我们就可以分布依次借助第1个点、第1和2个点、第1和2和3…个点中转，直到最后借助所有点中转，就会得到最短距离。
Floyd算法分析
很明显Floyd算法的时间复杂度是O(n3)，Floyd算法适用于有负权值的边的图，但不适用于有负权值回路（存在一条回路其总权值和为负）的图，很明显如果有负权值回路的话一直走该回路，花费就会达到无限小，无法到达终点。
今天药忘吃喽~
你的名字
小灰灰
╰半夏微凉°
港控/mmm°
还没有评论，来说两句吧...