The Confusion Is Real

UCS and Dijkstra's algorithm are taught in different courses (AI vs. algorithms), use different vocabulary (frontier vs. priority queue of vertices, g(n) vs. dist[v]), and somehow end up feeling like two separate things. They are not. UCS is Dijkstra's algorithm, restricted to a search problem and stopped early. Everything else is the same machinery.

The core shift: Dijkstra answers "what's the shortest distance to every node?" UCS answers "what's the cheapest way to reach one specific goal?" — and stops the moment it knows.

What Problem Each One Solves

Dijkstra's Algorithm Uniform Cost Search (UCS)
Problem type Single-source shortest path: find the shortest distance from one source to every other vertex Search problem: find the cheapest path from a start state to a goal state
Is the graph known upfront? Yes — usually a fixed, fully known graph (adjacency list/matrix) Not necessarily — the graph can be implicit, generated on demand via a successors(state) function (e.g. legal moves in a puzzle)
When does it stop? When the priority queue is empty — i.e. after computing distances to everything The instant the goal node is popped from the frontier

Same underlying optimization, different scope: Dijkstra computes the answer for the whole graph; UCS only computes as much of the graph as it needs to answer one question.

The Core Idea

Both algorithms maintain a priority queue ordered by accumulated path cost — called dist[v] in Dijkstra, g(n) in UCS. The loop is identical in spirit:

  1. Pop the node with the smallest accumulated cost.
  2. If you haven't finalized it yet, finalize it.
  3. Relax/expand its neighbors — i.e. offer them a path through the node you just finalized.
  4. Repeat.

Why the first pop of a node is guaranteed optimal: this relies on one assumption — all edge weights are non-negative. That means walking further down any path can only make it more expensive, never cheaper. So if some node X is popped with cost c, no path discovered later could possibly reach X more cheaply — any such path would have to pass through some frontier node with cost < c, which contradicts X being the smallest available. This is the entire proof of optimality, for both algorithms.

Pseudocode

Uniform Cost Search

def uniform_cost_search(problem):
    node = Node(state=problem.initial_state, cost=0)
    frontier = PriorityQueue(order_by=lambda n: n.cost)
    frontier.push(node, priority=0)
    explored = set()

    while True:
        if frontier.is_empty():
            return FAILURE
        node = frontier.pop()              # smallest g(n) first

        if problem.is_goal(node.state):
            return solution(node)          # stop the instant goal is popped

        if node.state not in explored:
            explored.add(node.state)
            for action, successor, step_cost in problem.successors(node.state):
                child = Node(
                    state=successor,
                    parent=node,
                    action=action,
                    cost=node.cost + step_cost,
                )
                if child.state not in explored:
                    frontier.push(child, priority=child.cost)

Dijkstra's Algorithm