Ford算法的改进算法

• 作者: 梁娟 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最短路 Ford算法 不含负回路网络 改进算法
• 年，卷（期）: 2015,（7）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 72-75,81
• 页数: 5页
• 分类号: tP301.6
• 字数: 3540字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2015.07.016

摘要

Ford算法是求解不含负回路网络中从源节点到其余各节点最短路径的经典算法。但每次逼近中，都要计算所有节点的入弧，重复计算量大，降低了计算效率。为此，文中通过引入两个数组和只计算权值变小的节点的所有出弧对Ford算法进行改进，改进后的算法既能快速地计算从源节点到其余各节点的最短路权值，又能更直观地找出最短路径。最后通过具体实例分析和仿真结果表明，改进算法不仅简化了计算量，降低了时间复杂度，而且增强了寻路直观性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	梁娟	南京邮电大学理学院	2	24	2.0	2.0