Finding the Lowest-Cost Path with Uniform Cost Search
Problem Setup
Scenario:Find the lowest-cost path from the start node S to the goal node G in a weighted directed graph. Different routes may reach the same node with different total costs.
Given:A directed graph with S as the start node and G as the goal node. Each connection has a non-negative edge cost, and the search keeps track of the best known cost to reach each node.
Task:Apply Uniform Cost Search step by step, update a node whenever a cheaper route is found, and determine the lowest-cost path from S to G together with its total cost.
Need a quick refresher? Review Uniform Cost theory
Weighted Graph
Arrows show the permitted direction of travel, and edge labels show the cost of each connection. Different routes to the same node may have different total costs.
Step-by-Step Priority Queue Matrix
Evaluating Node ↓/Target → | S | A | B | C | D | G |
|---|---|---|---|---|---|---|
| — | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 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.
Final Answer
The lowest-cost route from S to G is:
Total path cost:10
G was initially reached with a cost of 14, which later improved to 13 and then 10. Uniform Cost Search does not stop when the goal is first discovered; it continues until G has the lowest cost in the priority queue and is selected for expansion, confirming the shortest path.
Final Shortest Costs from S
Exam Takeaway
- Select the smallest cumulative cost, not the fewest edges: Uniform Cost Search expands the frontier node with the lowest known total cost from the start. A path with more edges can still be cheaper than one with fewer edges.
- Update tentative distances when a cheaper route is found: A node's first recorded distance may not be its shortest distance. Compare each new path cost with the current best value and replace it if the new route is cheaper.
- Distinguish discovered nodes from finalized nodes: With nonnegative edge weights, a node's shortest distance is finalized when it is removed as the minimum-cost entry from the priority queue. Merely discovering the goal does not justify stopping the search.