A Study on the K Shortest Paths Algorithm in a Transportation Network (Using Ordered Heap Tree)
Gang-Won Im, Seung-Muk Yang, Seongil Shin · Journal of the Eastern Asia Society for transportation studies/Journal of the Eastern Asia Society for Transportation Studies · 2005
We propose a modified version of 'a Lazy Version of Eppstein's k shortest paths Algorithm(LVEA)' which can find the k shortest paths in total time O(m+ n log n+ K log K) in the worst-case. The algorithm we propose, since the Link repeated paths are all eliminated when enumerating k shortest paths, is No link repeated paths algorithm that is suitable in a transportation network.