The Improved Dijkstra's Shortest Path Algorithm and Its Application

AbstractThe 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