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
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.
Depends on the cost functions used…
- 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.
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
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
The output of this test program should give:
[C, B, A, D, E, F]
If you un comment the
setCosts line, then you get: