计算机技术与发展Issue(7)：72-75,81,5.DOI:10.3969/j.issn.1673-629X.2015.07.016
Ford算法的改进算法
Improved Algorithm of Ford Algorithm
摘要
Abstract
Ford algorithm is a classical algorithm that finds the shortest path from the source node to other nodes in solving the network without negative loop. However,all incoming arcs weights are needed to be calculated from all nodes in each approximation,and the a-mount of repeated calculation increases which decreases the efficiency of the algorithm. Ford algorithm is improved in this paper by intro-ducing two arrays and calculating all outgoing arcs weights from nodes whose weight become smaller. The improved algorithm can both calculate the shortest path weights more quickly and find the shortest paths more directly from the source node to other nodes. Finally,the specific analysis and simulation results indicate that the improved algorithm not only simplifies the amount of calculation and reduces the time complexity,but also enhances the intuition of finding the shortest path.关键词
最短路/Ford算法/不含负回路网络/改进算法Key words
the shortest path/Ford algorithm/network without negative loop/improved algorithm分类
信息技术与安全科学引用本文复制引用
赵礼峰,梁娟..Ford算法的改进算法[J].计算机技术与发展,2015,(7):72-75,81,5.基金项目
国家自然科学基金资助项目(61070234,61071167) （61070234,61071167）
