The Improved Dijkstra's Shortest Path Algorithm and Its Application

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