A New Algorithm for Shortest Path in DAG
Tengfei Jiang · Computer Technology and Development · 2013
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 calculating loop-free network.