Package com.jgalgo.alg.shortestpath

Interface ShortestPathHeuristicSt

All Known Implementing Classes:

ShortestPathAStar, ShortestPathHeuristicStAbstract

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.

Author:

Barak Ugav

See Also:

ShortestPathSingleSource

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

Returns:

a default implementation of ShortestPathHeuristicSt