### Documentation / Algorithms / Shortest path

# 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]
```