Package com.jgalgo.alg.shortestpath

Class KShortestPathsStAbstract

java.lang.Object

com.jgalgo.alg.shortestpath.KShortestPathsStAbstract

All Implemented Interfaces:

KShortestPathsSt

Direct Known Subclasses:

KShortestPathsStBasedPathsTree

public abstract class KShortestPathsStAbstract
extends Object
implements KShortestPathsSt

Abstract class for computing the k-shortest paths in graphs.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
KShortestPathsStAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V, E> List<Path<V,E>>	computeKShortestPaths(Graph<V,E> g, WeightFunction<E> w, V source, V target, int k)	Compute the K shortest paths from a source vertex to a target vertex.

Methods inherited from class java.lang.Object

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

Constructor Details

KShortestPathsStAbstract

public KShortestPathsStAbstract()

Default constructor.

Method Details

computeKShortestPaths

public <V,
E> List<Path<V,E>> computeKShortestPaths(Graph<V,E> g,
 WeightFunction<E> w,
 V source,
 V target,
 int k)

Description copied from interface: KShortestPathsSt

Compute the K shortest paths from a source vertex to a target vertex.

If g is IntGraph, the returned object is a list of IPath. If g is IntGraph, prefer to pass IWeightFunction for best performance.

Specified by:

computeKShortestPaths in interface KShortestPathsSt

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - the graph

w - an edge weight function

source - the source vertex

target - the target vertex

k - the number of shortest paths to compute

Returns:

k shortest paths from the source to the target, or less if there are no such k paths