Uniform Cost Search: A Complete Solved Numerical Example
Scenario: City Transit Route Optimization
The Objective: Find the most cost-effective transit route from the starting station (S) to the final destination (G). Observe how Uniform Cost Search systematically explores paths based on exact ticket costs, updating its knowledge whenever a cheaper detour is discovered.
Core Mechanics▼
- Always Pop the Cheapest: Dijkstra runs on a Priority Queue. Instead of popping the oldest or newest node, you must always pop the unvisited node with the lowest cumulative cost, .
- Edge Relaxation: When evaluating neighbors, calculate the running total from the start. If this new total is cheaper than a neighbor's currently known cost, you "relax" the edge by updating it with the better score.
- Settled Nodes Are Locked: Once a node is popped as the absolute cheapest option, its shortest path is mathematically guaranteed. Lock it in the Closed List and never evaluate it again.
- The Goal Test (Pop, Don't Peek): Do not declare victory the moment the goal node appears in the queue! You must wait until the goal is officially popped to guarantee no cheaper path to it exists.
Step 1: Initial Map Configuration
Before we begin evaluating, here is the full structure of the spatial graph. Notice that Dijkstra's algorithm relies solely on exact edge weights, with no heuristics involved.
Step 2: Step-by-Step Resolution Trace
Watch the algorithm maintain the priority queue matrix and continuously relax edges until the optimal path is locked in.
Priority Queue Matrix
Evaluating Node ↓/Target → | S | A | B | C | D | G |
|---|---|---|---|---|---|---|
| S | — | 2 | 5 | ∞ | ∞ | ∞ |
| A | — | — | 5 | 5 | 9 | ∞ |
| B | — | — | — | 5 | 7 | 14 |
| C | — | — | — | — | 7 | 13 |
| D | — | — | — | — | — | 10 |
| G | — | — | — | — | — | — |
Calculation Breakdown
Evaluating Neighbors of S
Evaluating Neighbors of A
Evaluating Neighbors of B
Evaluating Neighbors of C
Evaluating Neighbors of D
Goal Reached at G
No valid unvisited neighbors to explore.
Step 3: Final Computed Path
Cheapest Path Found
Shortest Path to All Nodes
Final Takeaway
Look at the 'G' column in the matrix to see 'Edge Relaxation' in action as the algorithm repeatedly overwrites its own notes! It initially finds paths costing 14 and 13 before finally locking in the optimal 10-cost route, proving Dijkstra never settles until it mathematically guarantees the cheapest path.