Uniform Cost Search (Dijkstra's Algorithm) Theory Guide

Rules & Common Mistakes

• Exam Trap: Do Not Stop When a Number Appears in the Goal Column

  The moment a real cost appears in the Goal node's column, students instinctively circle it and call the trace done. That is wrong every single time. A number in the Goal column only means a path to the goal was discovered — it does not mean that path is the shortest one. A cheaper route through a different node might still be sitting unlocked in the same row. Keep going row by row until the Goal node is explicitly chosen as the Evaluating Node and its column receives a dash ($-$). That dash is the only valid termination signal.
• Exam Trap: Always Add to the Evaluating Node's Locked Cost — Not the Column Value

  This is the arithmetic mistake that silently corrupts an entire matrix. When calculating a neighbour's candidate cost, you must add the edge weight to the Evaluating Node's own locked cost — the number it held when it was selected and dashed. Never add the edge weight to whatever temporary number is currently sitting in the neighbour's column. That column value is a placeholder from a previous step. The formula is always: Evaluating Node's locked cost + edge weight = candidate cost for the neighbour.
• Exam Trap: Dashed Columns Are Permanently Dead — Never Update Them

  The moment a column receives a dash ($-$), that node's shortest path is mathematically finalized. If you are expanding a node and notice that one of its neighbours already has a dash in the current row, ignore that neighbour completely. Do not calculate a new cost for it. Do not erase the dash and overwrite it with a number. A dashed column is closed forever — and erasing one to update a value is always wrong. It will cascade bad numbers through every remaining row and cost you most of your marks on that question.
• Pro Tip: Tied Numbers in the Matrix? Break Alphabetically and Keep Moving

  If scanning a row reveals two unlocked columns with the exact same lowest cost, do not freeze. The algorithm will find the same optimal path cost regardless of which tied node you evaluate first — the final answer is guaranteed to be identical either way. To keep your trace consistent with standard marking rubrics, always break ties by picking the node whose letter comes first in the alphabet. Write that node on the left, dash its column, and continue. One second of decision, no marks lost.

Strengths, Weaknesses & When To Use It

When to use it:Reach for UCS whenever edge weights are different from each other and you need the guaranteed cheapest path — think varying flight prices, road distances with traffic delays, or network routing costs. If all the edge weights in your graph are identical, do not use UCS — just use Breadth-First Search, which gives you the same optimal answer with less overhead. And if your exam question provides heuristic values alongside the graph, do not use UCS either — upgrade to A*, which adds directional intelligence on top of UCS's cost-tracking and gets to the answer faster.

Uniform Cost Search vs. BFS vs. A*

Uniform Cost Search sits perfectly in the middle of the search algorithm family. It fixes the biggest blind spot of Breadth-First Search by actually reading edge weights — but it lacks the directional intelligence of A*, which uses a heuristic to aim directly at the goal. Think of UCS as the algorithm that learned to read price tags but still has no idea which way the destination is.

• The Price Tag (UCS vs. BFS): BFS counts hops and assumes every road costs the same. UCS reads the actual edge weights and tracks the real accumulated cost. On any graph where edge weights vary, BFS will likely hand you the wrong answer — UCS guarantees the right one.
• The Compass (UCS vs. A*): UCS has no $h(n)$ — it is completely blind to where the goal is and spills outward in every direction chasing the cheapest accumulated cost. A* adds a heuristic that pulls the search toward the goal, finding the exact same shortest path while evaluating far fewer nodes. Same answer, dramatically less work.
• The Optimality Guarantee: UCS is guaranteed to find the cheapest path as long as no edge weight is negative. BFS is only optimal under one very specific condition: every single edge in the graph costs exactly the same. The moment edge weights differ, BFS loses its optimality guarantee entirely.
• What Your Exam Is Actually Testing: When an exam asks you to trace both BFS and UCS on the same graph, that graph was deliberately designed with a trap — a short path with massive edge weights and a longer path with tiny ones. They want to see if you know that BFS will blindly grab the fewest-hop route and walk straight into the expensive trap, while UCS patiently takes the cheaper detour and wins.

Implementation Pseudocode

// UCS Matrix Method — each iteration of the loop = one new row in your table
// columns     = every node in the graph (e.g. S, A, B, C, G)
// cost[node]  = the current best accumulated cost sitting in that node's column
// locked[node]= true when a node has been dashed — its path is permanently finalized

function ucsMatrix(allNodes, startNode, goalNode, edges):

    // ── INITIALIZATION — ROW 1 ───────────────────────────────────────────

    // Write 0 under the Start node column — it costs nothing to be there already
    // Write Infinity under every other column — all other nodes are undiscovered
    for each node in allNodes:
        cost[node]   = Infinity
        locked[node] = false

    cost[startNode] = 0


    // ── MAIN LOOP — ONE ITERATION = ONE NEW MATRIX ROW ──────────────────

    while true:

        // ── SELECT — Find the lowest unlocked value in the current row ───

        // Scan every column — ignore anything already dashed (locked)
        // If two columns tie, break alphabetically
        evaluatingNode = null
        lowestCost     = Infinity

        for each node in allNodes:
            if not locked[node] and cost[node] < lowestCost:
                lowestCost     = cost[node]
                evaluatingNode = node

        // No unlocked node found — graph is disconnected, no path exists
        if evaluatingNode == null:
            return failure


        // ── TERMINATION TRAP — Only stop here, when the Goal is selected ─

        // A cost appearing in the Goal column is NOT termination
        // Termination only fires when the Goal becomes the Evaluating Node
        if evaluatingNode == goalNode:
            return cost[goalNode]  // this is your optimal path cost


        // ── LOCK — Place a dash in the Evaluating Node's column ──────────

        // This node's shortest path is now mathematically guaranteed — never touch it again
        locked[evaluatingNode] = true


        // ── EXPAND AND RELAX — Fill in every column for the new row ─────

        for each node in allNodes:

            if locked[node]:
                // This column already has a dash — skip it, never overwrite a locked column
                continue

            if node is a neighbour of evaluatingNode:

                // Calculate candidate cost: always use the Evaluating Node's locked cost
                candidateCost = cost[evaluatingNode] + edgeCost(evaluatingNode, node)

                if candidateCost < cost[node]:
                    // EDGE RELAXATION — new path is cheaper, overwrite the column value
                    cost[node] = candidateCost

                // else: existing value is equal or cheaper — copy it straight down, unchanged

            else:
                // Non-neighbour column — copy the value straight down from the previous row
                // cost[node] is already correct — no action needed


// ── INITIAL CALL ─────────────────────────────────────────────────────
// ucsMatrix(allNodes, startNode, goalNode, edges)

Time & Space Complexity

UCS Exam Questions Students Always Get Wrong

• I found the goal's cost in my matrix row, so I'm done, right?

  Not even close — and this mistake costs marks every time. A number appearing in the Goal column only means a path to the goal was discovered, not that it is the cheapest one. A cheaper route through another node might still be unlocked and waiting. You are only done when the Goal node is selected as the Evaluating Node and its column receives a dash ($-$). That dash is the only valid termination signal.

• Why do I have to keep writing $\infty$ in the columns? Can't I just leave them blank?

  Never leave a cell blank — it will cost you presentation marks and confuse your own trace. A blank cell implies the node does not exist or was never generated, which is a completely different statement from 'this node exists but has not been reached yet.' $\infty$ is the correct mathematical placeholder for an undiscovered node. Every cell in every row must hold exactly one thing: a cost, a dash, or $\infty$.

• Does it really matter which tied node I pick, or can I just choose either one?

  Mathematically, both choices lead to the same final optimal cost — so the algorithm is not broken either way. The problem is practical: if your trace diverges from your instructor's solution key, you cannot verify your own work or pinpoint where you went wrong. Always break ties alphabetically to stay consistent with standard grading rubrics. One second of discipline saves you ten minutes of confusion.

• I found a cheaper path to a node that already has a dash in its column. Should I update it?

  Never. A dash means that node's shortest path is mathematically proven and permanently locked in. If you erase a dash and overwrite the value, you have broken the algorithm's core guarantee and every subsequent row will be wrong. UCS ensures that the first time a node is selected as the Evaluating Node, the path used to reach it is already optimal — so any 'cheaper' path you think you found is an arithmetic error, not a discovery.