Finding the Lowest-Cost Path with A* Search

Last updated

Problem Setup

Scenario:Find the lowest-cost route from the start node S to the goal node G. Each connection has a travel cost, and each node has a heuristic estimate of the remaining cost to G.

Given:A weighted graph with S as the start and G as the goal. The graph provides the edge costs and heuristic values needed to calculate A*'s evaluation score, f(n) = g(n) + h(n).

Task:Apply A* step by step: track the path cost g(n), heuristic h(n), and f(n) values, choose which node to explore next, and determine the final path from S to G.

Need a quick refresher? Review A* Search theory

Search Graph

Arrows show the permitted direction of travel, edge labels show travel costs, and the values beside nodes show heuristic estimates of the remaining cost to G.

Start Node: S (Heuristic: 14)Goal Node: G (Heuristic: 0)
4
6
3
7
5
4
6
5
14
S
11
A
9
B
5
C
4
D
0
G
Want to edit this data in the live solver?

Step-by-Step Resolution

1

Evaluating Node: S

g(S)=0g (S) = 0h(S)=14h(S) = 14f(S)=14f(S) = 14
Open List

[ S(14) ]

Closed List

[ ]

Evaluating Neighbors
Evaluated neighbor A (via SA)
f=g(4)+h(11)=f = g (4) + h(11) = 15
Evaluated neighbor B (via SB)
f=g(6)+h(9)=f = g (6) + h(9) = 15
2

Evaluating Node: SA

g(A)=4g (A) = 4h(A)=11h(A) = 11f(A)=15f(A) = 15
Open List

[ SA(15), SB(15) ]

Closed List

[ S(14) ]

Evaluating Neighbors
Evaluated neighbor B (via SAB)Skipped: Worse path. We already found a cheaper way to B (Cost: 7 >= 6).
f=g(7)+h(9)=f = g (7) + h(9) = 16
Evaluated neighbor C (via SAC)
f=g(11)+h(5)=f = g (11) + h(5) = 16
3

Evaluating Node: SB

g(B)=6g (B) = 6h(B)=9h(B) = 9f(B)=15f(B) = 15
Open List

[ SB(15), SAC(16) ]

Closed List

[ S(14), SA(15) ]

Evaluating Neighbors
Evaluated neighbor D (via SBD)
f=g(11)+h(4)=f = g (11) + h(4) = 15
4

Evaluating Node: SBD

g(D)=11g (D) = 11h(D)=4h(D) = 4f(D)=15f(D) = 15
Open List

[ SBD(15), SAC(16) ]

Closed List

[ S(14), SA(15), SB(15) ]

Evaluating Neighbors
Evaluated neighbor G (via SBDG)
f=g(16)+h(0)=f = g (16) + h(0) = 16
5

Evaluating Node: SAC

g(C)=11g (C) = 11h(C)=5h(C) = 5f(C)=16f(C) = 16
Open List

[ SAC(16), SBDG(16) ]

Closed List

[ S(14), SA(15), SB(15), SBD(15) ]

Evaluating Neighbors
Evaluated neighbor D (via SACD)Skipped: Node D is already in the Closed List (already fully explored).
f=g(15)+h(4)=f = g (15) + h(4) = 19
Evaluated neighbor G (via SACG)Skipped: Worse path. We already found a cheaper way to G (Cost: 17 >= 16).
f=g(17)+h(0)=f = g (17) + h(0) = 17
6

Evaluating Node: SBDG

g(G)=16g (G) = 16h(G)=0h(G) = 0f(G)=16f(G) = 16
Open List

[ SBDG(16) ]

Closed List

[ S(14), SA(15), SB(15), SBD(15), SAC(16) ]

Evaluating Neighbors
No valid neighbors to explore.
7

Goal Reached: SBDG

Goal Found
Open List

[ ]

Closed List

[ S(14), SA(15), SB(15), SBD(15), SAC(16), SBDG(16) ]

Final Answer

A* reaches the goal through the lowest-cost path found during the search:

Optimal path: S → B → D → G

Total path cost:16

The chosen route costs 16, compared with 17 for the alternative through A and C. A* reaches the cheaper route by combining the cost already travelled with the estimated remaining cost when selecting nodes to explore.

Exam Takeaway

  • Compare nodes using the complete evaluation score: A* selects the open-list entry with the lowest f(n)=g(n)+h(n)f(n)=g(n)+h(n), not necessarily the lowest path cost or heuristic alone. If scores tie, follow the tie-breaking rule given in the question.
  • Keep the cheapest known path to each node: When multiple routes reach the same node, compare their g(n)g(n) values. A larger g(n)g(n) cannot improve that node's existing path when its heuristic is unchanged.
  • Check when the optimality guarantee applies: For A* graph search with nonnegative edge costs and a consistent heuristic, the goal's path cost is optimal when it is selected from the open list. Discovering the goal as a neighbor does not mean the search should stop immediately.