A* Search

graph

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Uses heuristics to find the shortest path more efficiently than Dijkstra's algorithm.

Time Complexity

Best

\mathrm{O}\left(E\right)

Avg

\mathrm{O}\left(E \log V\right)

Worst

\mathrm{O}\left(V^{2}\right)

Space Complexity

Aux

\mathrm{O}\left(V\right)

Open/closed sets + g/f scores — O(V) nodes

Pseudocode

1procedure A*(graph, start, end)

2f(n) = g(n) + h(n)

3while openSet is not empty do

4current = node with lowest f

5for each neighbor do

6if tentative_g < g(neighbor) then update