[1]赵礼峰,蒋腾飞.无回路网络最短路径的一种新算法[J].计算机技术与发展,2013,(02):105-107.
　ZHAO Li-feng,JIANG Teng-fei.A New Algorithm for Shortest Path in DAG[J].,2013,(02):105-107.
点击复制

无回路网络最短路径的一种新算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2013年02期
页码:
105-107
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
A New Algorithm for Shortest Path in DAG
文章编号:
1673-629X（2013）02-0105-03
作者:
赵礼峰; 蒋腾飞
南京邮电大学 理学院
Author(s):
ZHAO Li-feng; JIANG Teng-fei
关键词:
最短路; 无回路网络; 有效算法; 双向弧
Keywords:
shortest path; directed acyclic graph (DAG); effective algorithm; bi-directional arc
文献标志码:
A
摘要:
对于求解小规模无回路网络的最短路径这一问题,目前大多数算法都是基于Dijkstra算法或者穷举法的思想,不仅计算量大而且操作复杂.文中在深入分析已有算法的基础上,给出了一种新的简单易行的方法.该算法通过不断消去中间节点和弧以简化图的结构,既能快速地计算出源点到目的节点的最短路径,又能直观地找出最短路.最后算法通过具体实例分析表明,该算法不仅思想简便、易于操作,同时有效地降低了算法复杂度,是计算小规模无回路网络的一种行之有效的算法
Abstract:
For solving the shortest path on DAG,most of algorithms are based on Dijkstra algorithm or brute-force method,it's not only computationally expensive and complicated to operate. Based on the existing shortest path algorithm,propose a new simple method. The algorithm continuously deletes intermediate nodes and arcs to simplify the structure,not only can quickly calculate the shortest path from the source node to the destination node,but also find shortest paths easily. Finally algorithm through the concrete example analysis shows that,this algorithm is easy to operate,and at the same time,effective to reduce the algorithm complexity. It is a feasible algorithm of cal-culating loop-free network

相似文献/References:

[1]赵礼峰 宋常城 白睿.基于最小费用最大流问题的“排序”算法[J].计算机技术与发展,2011,(12):82.
　ZHAO Li-feng,SONG Chang-cheng,BAI Rui.Sequence Algorithm Based on Minimum Cost and Maximum Flow[J].,2011,(02):82.
[2]赵礼峰,梁娟. 最短路问题的Floyd改进算法[J].计算机技术与发展,2014,24(08):31.
　ZHAO Li-feng,LIANG Juan. Improved Floyd Algorithm for Shortest Paths Problem[J].,2014,24(02):31.
[3]赵礼峰,梁娟. Ford算法的改进算法[J].计算机技术与发展,2015,25(07):72.
　ZHAO Li-feng,LIANG Juan. Improved Algorithm of Ford Algorithm[J].,2015,25(02):72.

更新日期/Last Update: 1900-01-01