前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[图]最短路径-Floyd算法

[图]最短路径-Floyd算法

作者头像
王荣胜
发布2020-03-12 20:33:55
2.8K0
发布2020-03-12 20:33:55
举报
文章被收录于专栏:王荣胜的专栏文章分享

<!--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() ```

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-01-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档