About this visualization
Uniform-cost search always expands the frontier node with the smallest path cost g(n). It is Dijkstra's algorithm expressed as an AI search, and it finds the cheapest path whenever step costs are positive. Edit the edge costs and watch the priority queue reorder.
How it works
- Keep a priority queue ordered by g(n), the cost from the start.
- Pick the cheapest node; if it is the goal, its path is optimal.
- If a cheaper route to a frontier node is found, replace the old one.
Formulas used
- Time and space:
Worked example
On the Romania map from Arad to Bucharest, UCS expands Arad (g = 0), Zerind (75), Timisoara (118), Sibiu (140), Oradea (146), Rimnicu (220), Lugoj (229), Fagaras (239), Mehadia (299), Pitesti (317), Craiova (366) and Dobreta (374) — 12 nodes — before picking Bucharest with cost 418 via Arad → Sibiu → Rimnicu → Pitesti → Bucharest.
Enter these numbers in the simulator above to see every step.
Complexity and properties
| Worst case | |
|---|---|
| Space |
Complete and optimal when every step cost is at least ε > 0. It has no sense of direction, so it explores in all directions.
When to use it
- Cheapest-route problems with different edge costs.
- Seeing how Dijkstra's algorithm works as a search.
- Comparing with greedy search and A*.
Frequently asked questions
Is uniform-cost search optimal?
Yes, when all step costs are positive: the first time the goal is picked from the frontier its path is the cheapest.
What is the difference between UCS and Dijkstra's algorithm?
They behave the same; UCS is the AI-textbook formulation with a goal test, Dijkstra's algorithm computes shortest paths to every node.
What is the complexity of UCS?
time and space, where C* is the optimal cost and ε the smallest step cost.