Package com.jgalgo.alg.shortestpath

Class KShortestPathsStKatohIbarakiMine

java.lang.Object
com.jgalgo.alg.shortestpath.KShortestPathsStAbstract
com.jgalgo.alg.shortestpath.KShortestPathsStBasedPathsTree
com.jgalgo.alg.shortestpath.KShortestPathsStKatohIbarakiMine
All Implemented Interfaces:
KShortestPathsSt
public class KShortestPathsStKatohIbarakiMine extends KShortestPathsStBasedPathsTree
Katoh, Ibaraki and Mine algorithm for K shortest simple paths in undirected 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))\).

The total running time of this algorithm is \(O(k(m + n \log n))\). In practice Yen's algorithm may be faster for wide type of instances, especially when k is small, but this algorithm should theoretically be faster for large k.

Based on the paper 'An efficient algorithm for K shortest simple paths' by Katoh, Ibaraki and Mine.

Author:
Barak Ugav

  • Constructor Details

    • KShortestPathsStKatohIbarakiMine

      public KShortestPathsStKatohIbarakiMine()
      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