Package com.jgalgo.alg.shortestpath

Class KShortestPathsStBasedPathsTree

  • All Implemented Interfaces:
    KShortestPathsSt
    Direct Known Subclasses:
    KShortestPathsStHershbergerMaxelSuri, KShortestPathsStKatohIbarakiMine, KShortestPathsStYen
    public abstract class KShortestPathsStBasedPathsTree
extends KShortestPathsStAbstract
    A base class for computing the k-shortest paths from a source vertex to a target vertex in a graph using the compressed paths tree data structure.

    Given a set of paths, the compressed paths tree is a tree that represents the paths in a compressed form. The tree is built by looking at the longest common prefix among the paths, creating a node for the prefix and an edge for each deviation from the prefix, and then recursively building the tree for the suffix of the paths. This base algorithm find the k-th shortest paths in order to their weights, and maintain the paths tree of the k-1 shortest paths so far. For each node in the tree the best deviation path, which is a path that shares the prefix up to the node but deviates somewhere along the node local path, is computed and the node is added to a priority queue with the deviation path weight. The node with the minimum weight is extracted from the queue, the deviation path is added to the result list and to the paths tree, constant number of new nodes are added to the tree, and the best deviation path for each new node is computed and added to the queue. The classes extending this class are different in the way they compute the the best deviation path for a node. Some algorithms compute a single deviation path for each possible deviation point along a node local path and the best deviation of the node is the minimum among them, and some algorithms are able to compute the best deviation path in a single step. The latter algorithms can fail some times (see KShortestPathsStHershbergerMaxelSuri), and in that case the algorithm falls back to the former method. In general, computing the best deviation path in a single step is faster, but when the number of deviation points is small, sometimes it is faster to compute all the deviation paths and find the minimum among them, as the computation of the best deviation path in a single step is more complex.

    Author:
    Barak Ugav

    • Constructor Detail

      • KShortestPathsStBasedPathsTree

        public KShortestPathsStBasedPathsTree()
        Default constructor.