Package com.jgalgo.alg.shortestpath

Class ShortestPathAStar

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathHeuristicStAbstract

com.jgalgo.alg.shortestpath.ShortestPathAStar

All Implemented Interfaces:

ShortestPathHeuristicSt

public class ShortestPathAStar
extends ShortestPathHeuristicStAbstract

A* shortest path algorithm.

The A star (\(A^*\)) algorithm try to find the shortest path from a source to target vertex. It uses a heuristic that map a vertex to an estimation of its distance from the target position.

An advantage of the \(A^*\) algorithm over other ShortestPathSingleSource algorithm, is that it can terminate much faster for the specific source and target, especially if the heuristic is good.

The algorithm runs in \(O(m + n \log n)\) and uses linear space in the worse case. If the heuristic is good, smaller running time and space (!) will be used.

Author:

Barak Ugav

See Also:

• Wikipedia

Constructor Summary

Constructors

Constructor	Description
ShortestPathAStar()	Construct a new AStart algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.shortestpath.ShortestPathHeuristicStAbstract

computeShortestPath, computeShortestPath

Methods inherited from class java.lang.Object

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

Constructor Details

ShortestPathAStar

public ShortestPathAStar()

Construct a new AStart algorithm.

Please prefer using ShortestPathHeuristicSt.newInstance() to get a default implementation for the ShortestPathHeuristicSt interface.