The improved Dijkstra's shortest path algorithm
Shuxi Wang, Xing-qiu Zhao · 2011
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: ①. Its exiting mechanism is effective to undigraph but ineffective to digraph, or even gets into an infinite loop; ②. It hasn't addressed the problem of adjacent vertices in shortest path; ③. 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.