| 最短路问题的一种新动态规划算法 |
| |
| 引用本文： | 易颖华,叶祥企,杭海霞. 最短路问题的一种新动态规划算法[J]. 江西科学, 2008, 26(1): 89-91 |
| |
| 作者姓名： | 易颖华 叶祥企 杭海霞 |
| |
| 作者单位： | 江西师范大学数学与信息科学学院,江西,南昌,330022;江西师范大学数学与信息科学学院,江西,南昌,330022;江西师范大学数学与信息科学学院,江西,南昌,330022 |
| |
| 摘 要： | 结合并行处理及顺序（逆序）递推算法的思想，对有循环不带负弧的有向图中特别指定的2个节点之间的最短路问题提出了一种新的动态规划算法，且新算法在搜索结果上与狄克斯拉（Dijkstra）标号算法相同，但因为新算法采用了双向递推的思想，因而其搜索速度明显优于Dijkstra标号算法。
|
| 关 键 词： | 动态规划 最优策略 指标函数 |
| 文章编号： | 1001-3679（2008）01-0089-03 |
| 收稿时间： | 2007-10-15 |
| 修稿时间： | 2007-10-25 |
A New Dynamic Programming Algorithm for the Shortest Path Problem |
| |
| YI Ying-hua,YE Xiang-qi,HANG Hai-xia. A New Dynamic Programming Algorithm for the Shortest Path Problem[J]. Jiangxi Science, 2008, 26(1): 89-91 |
| |
| Authors: | YI Ying-hua YE Xiang-qi HANG Hai-xia |
| |
| Affiliation: | (Mathematics and Information Department,Jiangxi Normal University,Jiangxi Nanchang 330022 PRC) |
| |
| Abstract: | 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. |
| |
| Keywords: | Dynamic programming Optimal strategy Indicator function |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
