aStarSearch: A*-Search Algorithm

In huoston/shortestpath: Shortest Path Algorithm Visualization

Description

Use the A*-Search algorithm to solve a shortest path problem.

Usage

aStarSearch(graph, from, to, distance.heuristic = euclidean.vertex.distance)

Arguments

graph	The graph object.
from	The source vertex
to	The target vertex
distance.heuristic	The A* distance heuristic.

Details

A*-Search is a single-source algorithm which cannot deal with negative edge weights. Compared to Dijkstra's algorithm (dijkstra), it uses an euclidean distance heuristic to estimate the minimum distance to the target vertex and thereby rule out solutions. Thus, it is usually vastly faster than Dijkstra, but requires an euclidean problem instance.

Value

An spresults object.

See Also

setRandomVertexCoordinates and setVertexCoordinatesFromLayout to set vertex coordinates for a graph object. euclidean.vertex.distance for the default distance heuristic.

Examples

g <- randomGraph(6, euclidean=TRUE)
d <- aStarSearch(g, "A", "F")

plot(d)

for(step in d){
  print(step$min_dists)
}

huoston/shortestpath documentation built on May 25, 2019, 8:18 a.m.