Development of a Shortest Path Searching Algorithm Using Minimum Expected Weights
Yeong-Geun Ryu · The Journal of The Korea Institute of Intelligent Transport Systems · 2013
This paper developed a new shortest path searching algorithm based on Dijkstra`s algorithm and algorithm, so it guarantees to find a shortest path in efficient manner. In this developed algorithm, minimum expected weights implies the value that straight line distance from a visiting node to the target node multiplied by minimum link unit, and this value can be the lowest weights between the two nodes. In behalf of the minimum expected weights, at each traversal step, developed algorithm in this paper is able to decide visiting a new node or retreating to the previously visited node, and results are guaranteed. Newly developed algorithm was tested in a real traffic network and found that the searching time of the algorithm was not as fast as other algorithms, however, it perfectly found a minimum path in any case. Therefore, this developed algorithm will be effective for the domain of searching in a large network such as RGV which operates in wide area.