A* Search Algorithm Calculator

Read the Theory Guide →

Build a weighted graph with heuristic values, choose start and goal nodes, and run A* to see how the search evaluates nodes and finds a path.

What You Can Explore

  • Build and modify the graph by adding, connecting, moving, or deleting nodes.
  • Enter heuristic values and edge costs, then choose the Starting Point and Goal Point.
  • Switch between directed and undirected graphs to see how edge direction affects the search.
  • Step through the search to follow each node's g, h, and f values and the Open and Closed Lists.
Core Mechanics
▼
  • The Master Equation f(n)=g(n)+h(n)f(n) = g(n) + h(n): Always expand the node with the lowest total score. It combines the exact cost traveled so far g(n)g(n) with the estimated cost to finish h(n)h(n).
  • Never Overestimate (Admissibility): To guarantee the shortest path, your heuristic h(n)h(n) must be optimistic. It can guess lower than the true remaining cost, but never higher.
  • Open vs. Closed Lists: Discovered paths wait in the Open List. Once a node is expanded as the cheapest option, it locks into the Closed List and is never evaluated again.
  • The Goal Test Trap: A* only claims victory when the goal is popped from the Open List, not when it is first discovered. This prevents you from accidentally accepting a fast but expensive path!
Initializing Workspace...

Understanding Your Result

The route, cost, and step-by-step states all come from your graph, heuristic values, and selected start and goal. Use the intermediate states to see why nodes were explored and how the final route was reached.

  • The Total Path Cost is the accumulated cost of the route selected by the solver.
  • Each step shows the node selected for expansion and its current g, h, and f values, making the search order easier to follow.
  • Neighbors marked as skipped show a reason beside them. Read it to see why that neighbor was not added or updated in the Open List.
  • If the search is exhausted without reaching the goal, check that the selected nodes are connected by usable edges in the current graph direction.

Try These Experiments

Overestimate One Heuristic

Setup: Run the preloaded graph with S as the start and G as the goal, and note the path and total cost.

Action: Change the heuristic of node C from 5 to 20, then run Find Optimal Path again.

What to Observe: Compare the final path and cost with the first run, and check how the changed heuristic affects the order in which nodes are considered.

Takeaway: An overestimated heuristic can make a promising node look more expensive than it really is, causing A* to choose a more expensive route. Optimality depends on an admissible heuristic.

Make the Direct Edge Cheaper

Setup: Run the preloaded graph and note the path, total cost, and number of search steps.

Action: Change the cost of the edge from B to G from 12 to 4, then run Find Optimal Path again.

What to Observe: Compare the Open List and step order with the first run. Notice how the cheaper route brings G forward in the search.

Takeaway: Changing an edge cost can alter both the route selected and how quickly the goal becomes the best candidate for expansion.

Remove the Heuristic

Setup: Run the preloaded graph and note the nodes explored and the final route.

Action: Set the heuristic value of every node to 0 and run the solver again.

What to Observe: Compare the search order, number of steps, and final route with the original run.

Takeaway: With h(n)=0h(n) = 0, the heuristic no longer influences the search score, so the solver is guided only by the cost accumulated from the start.