Package com.jgalgo.alg.shortestpath

Class KShortestPathsStYen

java.lang.Object

com.jgalgo.alg.shortestpath.KShortestPathsStAbstract

com.jgalgo.alg.shortestpath.KShortestPathsStBasedPathsTree

com.jgalgo.alg.shortestpath.KShortestPathsStYen

All Implemented Interfaces:

KShortestPathsSt

public class KShortestPathsStYen
extends KShortestPathsStBasedPathsTree

Yen's algorithm for computing the K shortest paths between two vertices in a graph.

This implementation is based on the paths compressed tree (the base class), which looks very different from the original algorithm, but it is indeed the same algorithm. This way of maintaining the paths is more efficient than the original algorithm, and improvements such as Lawler's are not necessary.

The algorithms runs in \(O(nk(m+n \log n))\) time.

Author:

Barak Ugav

See Also:

• Wikipedia

Constructor Summary

Constructors

Constructor	Description
KShortestPathsStYen()	Create a new instance of the algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.shortestpath.KShortestPathsStAbstract

computeKShortestPaths

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

KShortestPathsStYen

public KShortestPathsStYen()

Create a new instance of the algorithm.

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