#8 A*-Searchalgorithm
Hi,
i have implemented the A*-algorithm using OpenJGraph.
In contrast to the search
algorithm already in the library, my algorithm computes
only the path
between two vertices and does not compute a spanning
tree to all other
vertices. Therefore it performes faster than the other
algorthim,
especially if a estimate function is given.
Besause of the slightly different result of both algrothims I
found it not
appropiate to make my algorithm a subclass of
ShortestPathAlgorithm.
Although AStarSearch.shortestPath() produces only a part
of the result that
WeightedGraphImpl.shortestPath() does, I have tried to
compare execution
times of the functions on different graphs. The graphs had
all 10000
vertices with ca. 25000 randomly placed edges.
I have included the program used to test the algortihms in
examples.SampleShortestPath.java.
I observed following execution times (in miliseconds) on
my computer (1 GHz Celeron, JDK
1.4.0 Server VM, Linux 2.4) after 100 executions of each
function.
AStarSearch.shortestPath() (with decent estime function):
448 (avg.) 1 (min) 1401 (max)
AStarSearch.shortestPath() (without estime function):
879 (avg.) 11 (min) 2690 (max)
WeightedGraphImpl.shortestPath():
20281 (avg.) 19501 (min) 21878 (max)
Greets
