摘要
对于求解小规模无回路网络的最短路径这一问题,目前大多数算法都是基于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.
出处
《计算机技术与发展》
2013年第2期105-107,110,共4页
Computer Technology and Development
基金
国家自然科学基金资助项目(61070234
61071167)
关键词
最短路
无回路网络
有效算法
双向弧
shortest path
directed acyclic graph （ DAG I
effective algorithm
bi-directionat arc
