A New Dynamic Programming Algorithm for the Shortest Path Problem
Hang Hai-xia · Jiangxi kexue · 2008
In this paper,unifying the thought of the parallel process and the forward(backward)recursion algorithm,a new dynamic programming algorithm is presented to solve the shortest path problem between two notes in the directed graph which is cyclic and without negative arc.The new algorithm is same in the search result with the Dijkstra label algorithm.Because it adopts bidirectional recursion method,so the search speed obviously surpasses the Dijkstra label algorithm.