The Improved Dijkstra's Shortest Path Algorithm and Its Application

被引：48

作者：

Wang Shu-Xi ^{[1
]}

机构：

[1] Univ Int Business & Econ, Sch Informat Technol, Beijing 100029, Peoples R China

来源：

2012 INTERNATIONAL WORKSHOP ON INFORMATION AND ELECTRONICS ENGINEERING | 2012年 / 29卷

关键词：

Shortest Path; Label Algorithm; Dijkstra; p-label; t-label;

D O I：

10.1016/j.proeng.2012.01.110

中图分类号：

TH [机械、仪表工业];

学科分类号：

120111 [工业工程];

摘要：

The shortest path problem exists in variety of areas. A well known shortest path algorithm is Dijkstra's, also called "label algorithm". Experiment results have shown that the "label algorithm" has the following issues: I.. Its exiting mechanism is effective to undigraph but ineffective to digraph, or even gets into an infinite loop; II. It hasn't addressed the problem of adjacent vertices in shortest path; III.. It hasn't considered the possibility that many vertices may obtain the "p-label" simultaneously. By addressing these issues, we have improved the algorithm significantly. Our experiment results indicate that the three issues have been effectively resolved. (C) 2011 Published by Elsevier Ltd. Selection and/or peer-review under responsibility of Harbin University of Science and Technology

引用

页码：1186 / 1190

页数：5