Package org.graph4j.shortestpath

Class AStarAlgorithm

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.AStarAlgorithm

All Implemented Interfaces:

SinglePairShortestPath

public class AStarAlgorithm
extends GraphAlgorithm
implements SinglePairShortestPath

A* algorithm finds the shortest path from a specified source vertex to a specified target vertex. The algorithm is guided by a heuristic function h(v) that estimates the distance from the vertex v to the target. Dijkstra's algorithm can be viewd as a special case of A* where no heuristic function is available: h(v)=0, for all v.

Author:

Cristian Ivan, Cristian Frăsinaru

Field Summary

Fields

Modifier and Type	Field	Description
protected int[]	before
protected double[]	cost
protected int	numSolved
protected int[]	size
protected boolean[]	solved
protected final int	source
protected final int	target
protected final int[]	vertices

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
AStarAlgorithm(Graph graph, int source, int target, AStarEstimator heuristic)	Creates an algorithm to find the shortest path between source and target.

Method Summary

Modifier and Type	Method	Description
protected void	compute()
protected Path	createPathEndingIn(int vi)
Path	findPath()	Returns the shortest path between source and target.
double	getPathWeight()	Returns the weight of the shortest path from the source to the target, or Double.POSITIVE_INFINITY if no path exists.
int	getSource()	Returns the source vertex number.
int	getTarget()	Returns the target vertex number.

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graph4j.shortestpath.SinglePairShortestPath

getGraph

Field Details

source

protected final int source

target

protected final int target

vertices

protected final int[] vertices

cost

protected double[] cost

before

protected int[] before

size

protected int[] size

solved

protected boolean[] solved

numSolved

protected int numSolved

Constructor Details

AStarAlgorithm

public AStarAlgorithm(Graph graph,
 int source,
 int target,
 AStarEstimator heuristic)

Creates an algorithm to find the shortest path between source and target.

Parameters:

graph - the input graph.

source - the source vertex number.

target - the target vertex number.

heuristic - the estimated distance from a vertex to the target.

Method Details

getSource

public int getSource()

Description copied from interface: SinglePairShortestPath

Returns the source vertex number.

Specified by:

getSource in interface SinglePairShortestPath

Returns:

the source vertex number.

getTarget

public int getTarget()

Description copied from interface: SinglePairShortestPath

Returns the target vertex number.

Specified by:

getTarget in interface SinglePairShortestPath

Returns:

the target vertex number.

findPath

public Path findPath()

Description copied from interface: SinglePairShortestPath

Returns the shortest path between source and target.

Specified by:

findPath in interface SinglePairShortestPath

Returns:

the shortest path from the source to the target, or null if no path exists

getPathWeight

public double getPathWeight()

Description copied from interface: SinglePairShortestPath

Returns the weight of the shortest path from the source to the target, or Double.POSITIVE_INFINITY if no path exists.

Specified by:

getPathWeight in interface SinglePairShortestPath

Returns:

the weight of the shortest path from the source to the target, or Double.POSITIVE_INFINITY if no path exists.

compute

protected void compute()

createPathEndingIn

protected Path createPathEndingIn(int vi)