K* (K Star): A Heuristic Search Algorithm for Finding the k Shortest Paths

This page provides information regarting a directed search algorithm, called K*, for finding the k shortest paths between a designated pair of vertices in a given directed weighted graph. K* has two advantages compared to current k-shortest-paths algorithms. First, K* operates on-the-fly, which means that it does not require the graph to be explicitly available and stored in main memory. Portions of the graph will be generated as needed. Second, K* can be guided using heuristic functions.

K* was developed in 2009 by Husain Aljazzar as part of his PhD work. K* was originally implemented as part of the DiPro toolset for the generation of counterexamples in probabilistic model checking. In 2017, Sebastian Haufe has implemented a Java workbench for the K* algorithm. It comprises a Java implementation of K*, based on the one included in DiPro, that is independent from the DiPro environment. We hope that this workbench will make it easier to apply K* to a large class of k-shortest-path problems in various domains.

Publications

  • Husain Aljazzar and Stefan Leue: K*: A Heuristic Search Algorithm for Finding the k Shortest PathsArtificial Intelligence, Volume 175, Number 18, December 2011.
    Download: [PDF]
  • Sebastian Haufe: A workbench for the K* algorithm. Bachelor Thesis, University of Konstanz, 2017.
    Download: [PDF]

Download Links

  • The K* Java workbench by Sebastian Haufe. This zip-file contains the code, interfaces, examples and documentation.
  • The K* algorithm was originally implemented as part of the DiPro tool. To obtain a copy of DiPro, visit the DiPro-page. The K* algorithm source can be found under src/dipro/alg/kStar.
  • This file contains files that were used to perform the experiments presented in the original K* paper published in Artificial Intelligence (see above.) It is not compatible with the K* Java workbench.