# The A* Shortest path algorithm

A* computes the shortest path from a node to another in a graph. It can eventually fail if the two nodes are in two distinct connected components.

In this A* implementation, the various costs (often called g, h and f) are given by a `org.graphstream.algorithm.AStar.Costs` class. This class must provide a way to compute:

• The cost of moving from a node to another, often called g;
• The estimated cost from a node to the destination, the heuristic, often noted h;
• f is the sum of g and h and is computed automatically.

By default the `org.graphstream.algorithm.AStar.Costs` implementation used uses a heuristic that returns 0 for any heuristic. This makes A an equivalent of the Dijkstra algorithm, but also makes it far less efficient.

## Complexity

Depends on the cost functions used…

## Reference

• Hart, P. E.; Nilsson, N. J.; Raphael, B. (1972). “Correction to “A Formal Basis for the Heuristic Determination of Minimum Cost Paths””. SIGART Newsletter 37: 28–29.

## Usage

The basic usage is to create an instance of A*, then to ask it to compute from a shortest path from one target to one destination, and finally to ask for that path:

The advantage of A* is that it can consider any cost function to drive the search. You can create your own cost functions implementing the `Costs` interface.

You can also test the default “distance” cost function on a graph that has “x” and “y” values. You specify the Cost function before calling the `compute(String,String)` method:

## Example

The output of this test program should give:

``````[C, B, A, D, E, F]
``````

If you un comment the `setCosts` line, then you get:

``````[C, F]
``````