floyd算法介绍
精选回答
高山流水 2024-05-28 16:31:34
1、Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
2、在计算机科学中,Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权)。虽然它不返回路径本身的细节,但是可以通过对算法的简单修改来重建路径。该算法的版本也可用于查找关系R的传递闭包,或(与Schulze投票系统相关)在加权图中所有顶点对之间的最宽路径。
3、Floyd-Warshall算法是动态规划的一个例子,并在1962年由Robert Floyd以其当前公认的形式出版。然而,它基本上与Bernard Roy在1959年先前发表的算法和1962年的Stephen Warshall中找到图形的传递闭包基本相同,并且与Kleene的算法密切相关 在1956年)用于将确定性有限自动机转换为正则表达式。算法作为三个嵌套for循环的现代公式首先由Peter Ingerman在1962年描述。
4、该算法也称为Floyd算法,Roy-Warshall算法,Roy-Floyd算法或WFI算法。
![](http://yyk.iask.sina.com.cn/pic/fimg/160992409012376971618.jpg)
相关推荐
游鉴湖秦观原文翻译
宋朝是文学作品发展的高峰时期,有很多文人留下了不少经典的作品。比如说苏轼、李清照、辛弃疾、秦观等一大批优秀的诗词作家,都有脍炙人口的作品。游鉴湖秦观原文翻译游鉴湖[宋]秦观画舫珠帘出缭墙,天风吹到芰荷乡。水光入...
展开详情雨果的创作生涯可分为几个时期
雨果1802年2月26日出生于法国东部城市贝桑松,出生6周后,雨果随父母到处奔波。雨果幼时便显露出极高的文学天赋,后来的创作产生了不小的影响。雨果的创作生涯可分为几个时期雨果的创作生涯可分为四个时期。第一个创作...
展开详情歌德的少年维特之烦恼是一部什么小说
歌德1749年8月28日出生于法兰克福镇的一个富裕家庭。小时候歌德的父亲非常严肃,相反,母亲用不同于父亲的温柔母爱来安慰、保护着歌德、鼓励和引导他的学习兴趣,努力培养歌德正确理解文学的能力。歌德的少年维特之烦恼...
展开详情李清照对项羽的评价
李清照,号易安居士,她改革了宋代时期的词风,对宋词的发展有着巨大的贡献,引领了宋代词风的发展。李清照写词极佳,她的诗作也是一绝,李清照的诗作代表《夏日绝句》,其中的“生当作人杰,死亦为鬼雄”为千古名句,流传至今...
展开详情李清照前后词风的变化
有“千古第一才女”之称的词人李清照,在宋代文学史上有着重要的地位,她开创了新的词体,将婉约的风格发挥到了极致,引领着宋代婉约词做的发展。李清照在古典文学史占据着重要的地位,冠绝一时,被誉为“婉约之词宗”、“词国...
展开详情