Bound Searching Algorithm for Shortest Path in a Network
Ruichun He, Guo Yao-huang · Journal of Southwest Jiaotong University · 2004
Many irrelevant vertexes must be searched in order to find the shortest path between two vertexes in a large network with Dijkstra algorithm, resulting in low efficiency. To improve the searching efficiency, a new searching algorithm, named bidirectional bound searching algorithm, was proposed. With this method, a shortest path from the source vertex to the terminal vertex via any vertex is determined first by bidirectional searching. This path is closed to or even the same as the shortest path to be found. The length of this path is then taken as a bound, and any vertex with larger label value than the bound in later calculations will not be considered. It was proved that the calculating efficiency of the new algorithm was as twice as that of the traditional Dijkstra algorithm.