Package com.jgalgo.alg.shortestpath

Class KShortestPathsStHershbergerMaxelSuri

java.lang.Object
com.jgalgo.alg.shortestpath.KShortestPathsStAbstract
com.jgalgo.alg.shortestpath.KShortestPathsStBasedPathsTree
com.jgalgo.alg.shortestpath.KShortestPathsStHershbergerMaxelSuri
All Implemented Interfaces:
KShortestPathsSt
public class KShortestPathsStHershbergerMaxelSuri extends KShortestPathsStBasedPathsTree
Hershberger, Maxel and Suri algorithm for K shortest simple paths in directed graphs.

The algorithm is similar to Yen's algorithm, but to compute the best 'replacement' path (deviation path, the next shortest path that replace at least one edge from the previous k-th shortest path) a more carful subroutine is used, running in time \(O(m + n \log n)\) using two shortest path trees. Yen's algorithm runs a S-T shortest path computation for each edge in the last k-th shortest path, therefore each such iteration runs in time \(O(n(m + n \log n))\). Unlike the undirected case, see KShortestPathsStKatohIbarakiMine, in directed graphs the fast replacement algorithm may fail to find a deviation path, in which case the regular Yen's algorithm is used.

The total running time of this algorithm is \(O(nk(m + n \log n))\) in the worst case, but in practice it usually runs in time \(O(k(m + n \log n))\).

Based on the paper 'Finding the k Shortest Simple Paths: A New Algorithm and its Implementation' by John Hershberger, Matthew Maxel and Subhash Suri.

Author:
Barak Ugav

  • Constructor Details

    • KShortestPathsStHershbergerMaxelSuri

      public KShortestPathsStHershbergerMaxelSuri()
      Create a new instance of the algorithm.

      Please prefer using KShortestPathsSt.newInstance() to get a default implementation for the KShortestPathsSt interface.

  • Method Details

    • setFastReplacementThreshold

      public void setFastReplacementThreshold(int threshold)
      Set the threshold for the fast replacement algorithm.

      Given a path \(P\), a replacement path \(P'\) is the shortest path with the same source and target vertices that replace at least one edge from \(P\). During the running of the algorithm, replacement paths are computed for different paths with different lengths. Yen's algorithm uses a black box S-T shortest path computation for each possible deviation edge, which is a time consuming operation. The fast replacement algorithm computes the replacement path in time \(O(m + n \log n)\) using two shortest path trees. In practice, Yen's solution might be faster, specifically when the path \(P\) is short, as the fast replacement algorithm is more complex and it's theoretical advantage is relevant when a large number of S-T computation are required in Yen's algorithm.

      This method sets a threshold for which for any path with length greater or equal than this threshold, the fast replacement algorithm is used. The default value is 50.

      Parameters:
      threshold - if the path is greater or equal to this threshold, the fast replacement algorithm is not used