KOPS - The Institutional Repository of the University of Konstanz
# K<sup>⁎</sup> : A heuristic search algorithm for finding the k shortest paths

Type of Publication: | Journal article |

Author: | Aljazzar, Husain; Leue, Stefan |

Year of publication: | 2011 |

Published in: | Artificial Intelligence ; 175 (2011), 18. - pp. 2129-2154. - ISSN 0004-3702 |

DOI (citable link): | https://dx.doi.org/10.1016/j.artint.2011.07.003 |

Summary: |
We present 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. We prove the correctness of K^{⁎} and determine its asymptotic worst-case complexity when using a consistent heuristic to be the same as the state of the art, O(m+nlogn+k), with respect to both runtime and space, where n is the number of vertices and m is the number of edges of the graph. We present an experimental evaluation of K^{⁎} by applying it to route planning problems as well as counterexample generation for stochastic model checking. The experimental results illustrate that due to the use of heuristic, on-the-fly search K^{⁎} can use less time and memory compared to the most efficient k-shortest-paths algorithms known so far. |

Subject (DDC): | 004 Computer Science |

Keywords: | k-shortest-paths problem, K^{⁎}, heuristic search, on-the-fly search |

Bibliography of Konstanz: | Yes |

Files | Size | Format | View |
---|---|---|---|

There are no files associated with this item. |

ALJAZZAR, Husain, Stefan LEUE, 2011. K^{⁎} : A heuristic search algorithm for finding the k shortest paths. In: Artificial Intelligence. 175(18), pp. 2129-2154. ISSN 0004-3702. Available under: doi: 10.1016/j.artint.2011.07.003

@article{Aljazzar2011heuri-19330,
title={K^{⁎} : A heuristic search algorithm for finding the k shortest paths},
year={2011},
doi={10.1016/j.artint.2011.07.003},
number={18},
volume={175},
issn={0004-3702},
journal={Artificial Intelligence},
pages={2129--2154},
author={Aljazzar, Husain and Leue, Stefan}
}