I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of it. And did read about other implementations with the help of http://liinwww.ira.uka.de/bibliography/Theory/k-path.html
But in every paper there is a reference to multiple others citing improved performance in a different scenario. Ultimately too many options and tough to choose one. Hence can some one please provide the reference to most optimized sequential version of finding k-shortest path.
EDIT: Another problem with improved implementation of yen's algorithm is that one cant work with it in parallel. i.e. if I am finding kth shortest path from node 1 to node 100, then in mean time I cannot use it to find from a node to some other node. This is because it removes some nodes and arcs from graph in midst of computation.
The problem with eppstein again is that it uses its own data structure. There are many issues with it. Firstly I will have to construct it to use and the graph in my case is a large graph. The data structure is different for the start and terminal nodes respectively and same data structure cannot be used for other pair. Ultimately resulting in high memory utilization when using multiple instances of the algorithm.
EDIT2: Sorry, this is my fault for lack of clarity, What I basically meant was that One should be able to run multiple instances of the algorithm in parallel. With improvised version of Yen algorithm one cannot do that. Basically a sequential algorithm that can have multiple instances (instances and not parallelism in the algorithm) of it running in parallel.
Secondly, in EDIT1, both of the comments are not a comparison but rather a small discussion. Due to inability to find satisfactory loopless shortest paths, I came across Prof.Eppstein paper compromising on loops for performance. What I am basically looking for is a loopless k-shortest path sequential algorithm with less memory utilization (in my case I am dealing with large road networks) which can scale for very large graphs (over 50k nodes).
Thanks a lot.