Package com.jgalgo.alg

Interface ShortestPathHeuristicST

public interface ShortestPathHeuristicST

Shortest path algorithm that uses a distance heuristic function.

Given a source and target vertices, and a heuristic function that maps each vertex to distance approximation of its distance to the target, the algorithm attempt to find the shortest path from the source to target. An advantage of such algorithm over other ShortestPathSingleSource algorithms, is that it can terminate much faster for the specific source and target, especially if the heuristic is good.

Differing from the regular ShortestPathSingleSource, algorithms implementing this interface attempt to find the shortest path between a single source and a single target, rather than a single source and all other vertices as targets. Therefore, the algorithm can terminate after performing and using less than linear (in the graph size) operations and space.

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:

ShortestPathSingleSource

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
<V,E> Path<V,E>	computeShortestPath(Graph<V,E> g, WeightFunction<E> w, V source, V target, ToDoubleFunction<V> vHeuristic)	Compute the shortest path between two vertices in a graph.
IPath	computeShortestPath(IntGraph g, IWeightFunction w, int source, int target, IntToDoubleFunction vHeuristic)	Compute the shortest path between two vertices in an int graph.
static ShortestPathHeuristicST.Builder	newBuilder()	Create a new heuristic shortest path algorithm builder.
static ShortestPathHeuristicST	newInstance()	Create a new shortest path algorithm with heuristic.

Method Detail

computeShortestPath

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

Compute the shortest path between two vertices in a graph.

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 - a graph

w - an edge weight function

source - a source vertex

target - a target vertex

vHeuristic - a heuristic function that map each vertex to double. The heuristic should be close to the real distance of each vertex to the target.

Returns:

the short path found from source to target

computeShortestPath

IPath computeShortestPath(IntGraph g,
                          IWeightFunction w,
                          int source,
                          int target,
                          IntToDoubleFunction vHeuristic)

Compute the shortest path between two vertices in an int graph.

Parameters:

g - a graph

w - an edge weight function

source - a source vertex

target - a target vertex

vHeuristic - a heuristic function that map each vertex to double. The heuristic should be close to the real distance of each vertex to the target.

Returns:

the short path found from source to target

newInstance

static ShortestPathHeuristicST newInstance()

Create a new shortest path algorithm with heuristic.

This is the recommended way to instantiate a new ShortestPathHeuristicST object. The ShortestPathHeuristicST.Builder might support different options to obtain different implementations.

Returns:

a default implementation of ShortestPathHeuristicST

newBuilder

static ShortestPathHeuristicST.Builder newBuilder()

Create a new heuristic shortest path algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build ShortestPathHeuristicST objects