K*: Heuristics-Guided, On-the-Fly k Shortest Paths Search

Date Added: May 2009
Format: PDF

In this paper, the authors consider the K-Shortest-Paths Problem (KSP) which is about finding the k shortest paths from a start vertex s to a target vertex t in a directed weighted graph G for an arbitrary natural number k. Application domain examples for KSP problems include logistics, finance analysis, scheduling, sequence alignment, networking and many other optimisation applications. The initial motivation for their work stems from work on the generation of counter examples for stochastic model checking, which can be cast as a KSP problem.