K-Simple Shortest Paths Algorithms

Abstract - The generalization of the shortest path called multiple paths, or k-shortest path, finds k paths where the first path is shortest, and the remaining k-1 paths are in increasing lengths. K shortest path may be simple or non-simple. K Shortest Path problems are usually solved using Yen's algorithm, M-P algorithm, KSP-SPR, Heuristic search, A* algorithm, V-F algorithm, Lawlers Algorithm, etc. This paper provides the analysis and comparative study of some of the top k simple shortest path algorithms, which are very helpful in finding the multiple paths in road networks. Keywords - K shortest paths, Simple paths, Path finding, Deviation path, Spur path, Root path, Multiple path.