org.jgrapht.alg.shortestpath

Class ALTAdmissibleHeuristic<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.ALTAdmissibleHeuristic<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

AStarAdmissibleHeuristic<V>

public class ALTAdmissibleHeuristic<V,E>
extends Object
implements AStarAdmissibleHeuristic<V>

An admissible heuristic for the A* algorithm using a set of landmarks and the triangle inequality. Assumes that the graph contains non-negative edge weights.

The heuristic requires a set of input nodes from the graph, which are used as landmarks. During a pre-processing phase, which requires two shortest path computations per landmark using Dijkstra's algorithm, all distances to and from these landmark nodes are computed and stored. Afterwards, the heuristic estimates the distance from a vertex to another vertex using the already computed distances to and from the landmarks and the fact that shortest path distances obey the triangle-inequality. The heuristic's space requirement is $O(n)$ per landmark where n is the number of vertices of the graph. In case of undirected graphs only one Dijkstra's algorithm execution is performed per landmark.

The method generally abbreviated as ALT (from A*, Landmarks and Triangle inequality) is described in detail in the following paper which also contains a discussion on landmark selection strategies.

• Andrew Goldberg and Chris Harrelson. Computing the shortest path: A* Search Meets Graph Theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA' 05), 156--165, 2005.

Note that using this heuristic does not require the edge weights to satisfy the triangle-inequality. The method depends on the triangle inequality with respect to the shortest path distances in the graph, not an embedding in Euclidean space or some other metric, which need not be present.

In general more landmarks will speed up A* but will need more space. Given an A* query with vertices source and target, a good landmark appears "before" source or "after" target where before and after are relative to the "direction" from source to target.

Author:

Dimitrios Michail

Constructor Summary

Constructors

Constructor and Description
ALTAdmissibleHeuristic(Graph<V,E> graph, Set<V> landmarks) Constructs a new AStarAdmissibleHeuristic using a set of landmarks.

Method Summary

Modifier and Type	Method and Description
double	getCostEstimate(V u, V t) An admissible heuristic estimate from a source vertex to a target vertex.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ALTAdmissibleHeuristic

public ALTAdmissibleHeuristic(Graph<V,E> graph,
                              Set<V> landmarks)

Constructs a new AStarAdmissibleHeuristic using a set of landmarks.

Parameters:

graph - the graph

landmarks - a set of vertices of the graph which will be used as landmarks

Throws:

IllegalArgumentException - if no landmarks are provided

IllegalArgumentException - if the graph contains edges with negative weights

Method Detail

getCostEstimate

public double getCostEstimate(V u,
                              V t)

An admissible heuristic estimate from a source vertex to a target vertex. The estimate is always non-negative and never overestimates the true distance.

Specified by:

getCostEstimate in interface AStarAdmissibleHeuristic<V>

Parameters:

u - the source vertex

t - the target vertex

Returns:

an admissible heuristic estimate