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

Download Now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 238.8 KB