Package com.jgalgo.alg

Interface KShortestPathsST

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. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

ShortestPathST, ShortestPathSingleSource

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	KShortestPathsST.Builder	A builder for KShortestPathsST objects.

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

Method Detail

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. The KShortestPathsST.Builder might support different options to obtain different implementations.

Returns:

a default implementation of KShortestPathsST

newBuilder

static KShortestPathsST.Builder newBuilder()

Create a new K shortest paths algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build KShortestPathsST objects