Edit the graph and the cost on each link, pick a start and a goal, then press Play. UCS always expands the cheapest unexplored route first, using a priority queue, so the first time it reaches the goal it has found the cheapest path.
Not found yetIn the queueExpanding nowFinal costCheapest pathThe number on a link is its cost. "cost" under a node is the cheapest total found so far.
Step 0 of 0
Order of expansion
Nodes appear here in the order they leave the queue. The number beside each one is its final cost from the start.
Adjacency table
Every node with its links and their costs. It updates as you edit the graph. Click a row to select that node.
Node
Connected to (cost)
Best cost
Status
The algorithm
The highlighted lines are the ones running in the current step.
Uniform Cost Search (UCS) is a graph search algorithm for graphs whose links have different costs. It always expands the node with the lowest total cost so far, using a priority queue. Because it never settles a node until no cheaper route can exist, the first time it takes the goal out of the queue, the path it found is guaranteed to be the cheapest one.
O((V + E) log V)
Time complexity with a binary-heap priority queue
O(V)
Space complexity — the queue and the cost table can hold every node
Optimal
Always finds the cheapest path when every cost is zero or more
Priority queue
Core data structure — the cheapest entry always leaves first
How it works
Put the start node in the priority queue with a cost of 0.
Take out the entry with the lowest cost. That node's cost is now final, because every other route in the queue is at least as expensive.
If it is the goal, stop. Follow the parent links back to the start to read off the cheapest path.
Otherwise look at each neighbour that is not final yet. Its new cost is the current node's cost plus the link cost.
If the neighbour is new, add it to the queue. If the new cost beats the one it already has, update its entry and remember the new parent. Otherwise ignore it.
Repeat from step 2 until the goal is taken out or the queue is empty.
Key properties
Cost, not hops: UCS cares about the total cost of a path, not how many links it has. A longer path made of cheap links can beat a direct but expensive link.
Costs cannot be negative: the guarantee that a node's cost is final when it leaves the queue only holds when no link has a negative cost.
Complete and optimal: it finds a path whenever one exists and the path it returns is the cheapest.
Explores in all directions: it spreads outward in rings of increasing cost and has no idea where the goal is, so it can explore many nodes that are far from it.
Related algorithms: with equal costs it behaves like BFS. Run to completion without a goal it is Dijkstra's algorithm. Adding a guess of the remaining cost turns it into A*.
Worked example
Same graph as the default example in the Visualizer. Numbers on the links are costs. Find the cheapest path from A to G.
Default map. Filled nodes: start A and goal G.
Queue A:0.
Pop A (0). Add B:4, C:2, D:7.
Pop C (2). B via C = 3 (better than 4), D via C = 5 (better than 7), F = 10 (new).
Pop B (3). E = 8 (new).
Pop D (5). F via D = 9 (better than 10), H = 14 (new).
Pop E (8). G = 11 (new).
Pop F (9). G via F = 15 (worse, keep 11); H via F = 12 (better than 14).
Pop G (11). It is the goal, so stop.
Cheapest path: A → C → B → E → G, total cost 11. A node's cost is final only when it leaves the queue.
Where UCS is used
Route planning
Finding the shortest or cheapest way between two places on a map.
Network routing
Sending data along the lowest-latency or lowest-cost links.
Game pathfinding
Moving units across terrain where some tiles, like mud or water, cost more to cross.
Travel booking
Finding the cheapest chain of flights or trains with several connections.
Robot planning
Choosing motions that use the least energy or time to reach a target.
AI search problems
Solving puzzles where every move has a price and you want the cheapest solution.
Switch back to the Visualizer tab to build a graph, set the link costs, and watch each of these steps happen.