计算机技术与发展Issue(2)：105-107,111,4.DOI:10.3969/j.jssn.1673-2013.02.026
无回路网络最短路径的一种新算法
A New Algorithm for Shortest Path in DAG
摘要
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.关键词
最短路/无回路网络/有效算法/双向弧Key words
shortest path/directed acyclic graph (DAG)/effective algorithm/bi-directional arc分类
信息技术与安全科学引用本文复制引用
赵礼峰,蒋腾飞..无回路网络最短路径的一种新算法[J].计算机技术与发展,2013,(2):105-107,111,4.基金项目
国家自然科学基金资助项目(61070234,61071167) （61070234,61071167）
