无回路网络最短路径的一种新算法  

A New Algorithm for Shortest Path in DAG

作　　者：赵礼峰[1] 蒋腾飞[1] 

机构地区：[1]南京邮电大学理学院,江苏南京210003

出　　处：《计算机技术与发展》2013年第2期105-107,110,共4页Computer Technology and Development

基　　金：国家自然科学基金资助项目(61070234;61071167)

摘　　要：对于求解小规模无回路网络的最短路径这一问题,目前大多数算法都是基于Dijkstra算法或者穷举法的思想,不仅计算量大而且操作复杂。文中在深入分析已有算法的基础上,给出了一种新的简单易行的方法。该算法通过不断消去中间节点和弧以简化图的结构,既能快速地计算出源点到目的节点的最短路径,又能直观地找出最短路。最后算法通过具体实例分析表明,该算法不仅思想简便、易于操作,同时有效地降低了算法复杂度,是计算小规模无回路网络的一种行之有效的算法。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.

关 键 词：最短路 无回路网络 有效算法 双向弧 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]