最短路问题的一种新动态规划算法

A New Dynamic Programming Algorithm for the Shortest Path Problem

结合并行处理及顺序(逆序)递推算法的思想,对有循环不带负弧的有向图中特别指定的2个节点之间的最短路问题提出了一种新的动态规划算法,且新算法在搜索结果上与狄克斯拉(Dijkstra)标号算法相同,但因为新算法采用了双向递推的思想,因而其搜索速度明显优于Dijkstra标号算法。

In this paper, unifying the thought of the parallel process and the torward（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.