Package com.jgalgo

Interface ShortestPathWithHeuristic

public interface ShortestPathWithHeuristic

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.

Author:

Barak Ugav

See Also:

ShortestPathSingleSource

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
Path	computeShortestPath(Graph g, WeightFunction w, int source, int target, IntToDoubleFunction vHeuristic)	Compute the shortest path between two vertices in a graph.
static ShortestPathWithHeuristic.Builder	newBuilder()	Create a new heuristic shortest path algorithm builder.

Method Detail

computeShortestPath

Path computeShortestPath(Graph g,
                         WeightFunction w,
                         int source,
                         int target,
                         IntToDoubleFunction vHeuristic)

Compute the shortest path between two vertices in a 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

newBuilder

static ShortestPathWithHeuristic.Builder newBuilder()

Create a new heuristic shortest path algorithm builder.

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

Returns:

a new builder that can build ShortestPathWithHeuristic objects