[图]最短路径-Floyd算法

<!--more--> > Floyd算法（Floyd-Warshall algorithm）又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 -来自百度百科 前一篇文章：[第六章 图-Dijkstra算法](https://study.sqdxwz.com/index.php/archives/13/) 我们已经学习过了单源最短路径求解方法，这次我们来学习所有顶点间（任意两点间）的最短路径求解方法-Floyd算法。 对于求解任意两点最短路径的方式，我们也可以采用简单暴力将Dijkstra算法循环n遍（假设存在有n个顶点），也是可以求解任意两点间距离的，但是人类社会之所以会进步，难道仅仅是会使用筷子？还是好好学习更先进的算法-Floyd算法吧！ **注：**采用此暴力的时间复杂度为：O(n^3）。

# Floyd算法 开始之前我们需要了解到的一些知识点： 1.稀疏的图，采用n次Dijkstra比较出色； 稠密的图，采用Floyd算法比较好； 2.Floyd算法可以处理带负边的图； 3.同时也被用于计算有向图的传递闭包； 4.Floyd-Warshall算法的时间复杂度为O(n^3），空间复杂度为O(n^2）。 ## 1.算法思路 1.初始化，设置一个n阶方阵，令其对角线的元素为0，若存在<\vi,vj>,则对应元素为权值，否则为∞（过程1其实就是建立一个[邻接矩阵](https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5/9796080?fr=aladdin)）； 2.逐步试着在原路径中增加中间顶点，若加入中间顶点后路径变短，则进行修改，否则，维持原值； 3.进行所有顶点的试探，直至进行全部循环，算法结束。 ## 2.代码实现 ```python import numpy as np N = 4 M = 100 edge = np.mat([[0,2,6,4],[M,0,3,M],[7,M,0,1],[5,M,12,0]]) A = edge[:] path = np.zeros((N,N)) def Floyd(): for i in range(N): for j in range(N): if(edge[i,j] != M and edge[i,j] != 0): path[i][j] = i print('init:') print(A,'\n',path) for a in range(N): for b in range(N): for c in range(N): if(A[b,a]+A[a,c]<A[b,c]): A[b,c] = A[b,a] + A[a,c] path[b][c] = path[a][c] print('result:') print(A,"\n",path) if __name__ == "__main__": Floyd() ```