Package com.jgalgo.alg.shortestpath

Interface ShortestPathSt

All Known Implementing Classes:

ShortestPathStAbstract, ShortestPathStBidirectionalBfs, ShortestPathStBidirectionalDijkstra

public interface ShortestPathSt

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

Given a graph \(G=(V,E)\), and a weight function \(w:E \rightarrow R\), one might ask what is the shortest path 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 a path. It differ from the more known ShortestPathSingleSource, as it does not compute the paths from a source to all vertices, only to a specific target. This might be more efficient in some cases, as less than linear time and space can be used.

A variant with a heuristic distance function is also available, see ShortestPathHeuristicSt.

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

Author:

Barak Ugav

See Also:

ShortestPathSingleSource, ShortestPathAllPairs, ShortestPathHeuristicSt

Method Summary

Modifier and Type	Method	Description
default <V,E> Path<V,E>	computeShortestPath(Graph<V,E> g, WeightFunction<E> w, V source, V target)	Compute the shortest path from a source vertex to a target vertex.
<V,E> ObjectDoublePair<Path<V,E>>	computeShortestPathAndWeight(Graph<V,E> g, WeightFunction<E> w, V source, V target)	Compute the shortest path from a source vertex to a target vertex, and its weight.
static ShortestPathSt	newInstance()	Create a new S-T shortest path algorithm object.

Method Detail

computeShortestPath

default <V,E> Path<V,E> computeShortestPath(Graph<V,E> g,
                                                        WeightFunction<E> w,
                                                        V source,
                                                        V target)

Compute the shortest path from a source vertex to a target vertex.

If g is an IntGraph, a IPath object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

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

Returns:

the shortest path from the source to the target, or null if there is no path

computeShortestPathAndWeight

<V,E> ObjectDoublePair<Path<V,E>> computeShortestPathAndWeight(Graph<V,E> g,
                                                                           WeightFunction<E> w,
                                                                           V source,
                                                                           V target)

Compute the shortest path from a source vertex to a target vertex, and its weight.

If g is an IntGraph, a IPath object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

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

Returns:

a pair of the shortest path from the source to the target, and its weight, or null if there is no path

newInstance

static ShortestPathSt newInstance()

Create a new S-T shortest path algorithm object.

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

Returns:

a default implementation of ShortestPathSt