| 引用本文: | 王志坚,韩伟一,李一军.具有多条最短路径的最短路问题[J].哈尔滨工业大学学报,2010,42(9):1428.DOI:10.11918/j.issn.0367-6234.2010.09.017 |
| WANG Zhi-jian,HAN Wei-yi,LI Yi-jun.Shortest path problem with multiple shortest paths[J].Journal of Harbin Institute of Technology,2010,42(9):1428.DOI:10.11918/j.issn.0367-6234.2010.09.017 |
|
| 摘要: |
| 尽管Dijkstra算法是解决正权单源点最短路问题公认的最好算法,但它仅能求得从源点到指定点的一条最短路径,为了给出从源点到指定点的所有最短路径,通过改进临时标号过程,得到了修正的Dijkstra算法.修正后的算法得到的不再是最短路径树,而是最短路径图.相对于原算法,修正后的算法不仅更加简便,而且应用Yen算法能够按照边数由少到多的顺序罗列出所有的最短路径. |
| 关键词: 算法 最短路问题 Dijkstra算法 Yen算法 |
| DOI：10.11918/j.issn.0367-6234.2010.09.017 |
| 分类号:TP301.6 |
| 基金项目:国家自然科学基金资助项目(90924015);哈尔滨工业大学青年优秀基金资助项目(2009036) |
|
| Shortest path problem with multiple shortest paths |
|
WANG Zhi-jian, HAN Wei-yi, LI Yi-jun
|
|
School of Management,Harbin Institute of Technology,150001,China
|
| Abstract: |
| Though Dijkstra algorithm is the best known algorithm to solve the shortest path problem with nonnegative weight,it can only get one path from the source vertex to a designated vertex.In order to present all shortest paths from the source vertex to a designated vertex,the revised Dijkstra algorithm is obtained by improving the temporary label updating process.As a result,the revised algorithm gives the shortest path graph other than the shortest path tree.Compared with Dijkstra algorithm,the revised algorithm is simple,and all shortest paths can be given according to the number of edge by applying Yen algorithm. |
| Key words: algorithm the shortest path problem Dijkstra algorithm Yen algorithm |
