Interface KShortestPathsSt

All Known Implementing Classes:

KShortestPathsStAbstract, KShortestPathsStBasedPathsTree, KShortestPathsStHershbergerMaxelSuri, KShortestPathsStKatohIbarakiMine, KShortestPathsStYen

public interface KShortestPathsSt

An algorithm for computing the K shortest paths between two vertices in a graph.

Given a graph \(G=(V,E)\), and a weight function \(w:E \rightarrow R\), one might ask what are the K shortest paths from a source vertex to a target vertex, where the 'shortest' is defined by comparing the sum of edges weights of each path. This interface computes such paths. It differ from ShortestPathSt, as it computes multiple paths, and not just one.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

• ShortestPathSt
• ShortestPathSingleSource

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.
static KShortestPathsSt	newInstance()	Create a new K shortest paths algorithm object.

Method Details

computeKShortestPaths

<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.

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

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

newInstance

static KShortestPathsSt newInstance()

Create a new K shortest paths algorithm object.

This is the recommended way to instantiate a new KShortestPathsSt object.

Returns:

a default implementation of KShortestPathsSt