Uninformed search

Dijkstra's Algorithm

Always expand the closest unvisited node — that's the shortest path.

On the Sydney → London problem, Dijkstra's Algorithm finds: Sydney → Colombo → Dubai → London — total 22.0h.

The idea

Dijkstra's Algorithm finds the cheapest (shortest) path from one starting node to every other node in a graph where edges have costs (weights). It works by always expanding the node it can currently reach most cheaply, locking in that cost, and repeating until done. It is exactly the same algorithm as Uniform-Cost Search (UCS) in AI — different name, same idea.

How it works

Give every node a tentative cost g = distance from the start. The start node gets g = 0; every other node starts at infinity (unknown/unreachable so far).
Put the start node into OPEN, the frontier of nodes waiting to be expanded, ordered by lowest g first.
Pull the node with the smallest g out of OPEN. This is the closest unvisited node — its shortest distance is now final.
Move that node into CLOSED (already expanded/visited) so you never process it again.
Look at each neighbor of that node. Compute a candidate cost: g(current) + weight of the edge to the neighbor.
If that candidate is cheaper than the neighbor's current g, update the neighbor's g and record the current node as its parent (so you can trace the path back later).
Add or update that neighbor in OPEN with its new, better cost.
Repeat from step 3 until OPEN is empty (you've found shortest paths to everything reachable) or you pull out your goal node.

See it step by step

Watch Dijkstra's Algorithm search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Start at Sydney. OPEN (the frontier) holds just Sydney.

Expanding

OPEN — frontier

CLOSED — traversal

Path so far

Cost so far

Step 1 / 8

OPEN, CLOSED & the data structures

OPEN (the frontier) is a priority queue ordered by g, the cost from the start — this is the heart of Dijkstra, because always pulling the smallest g is what guarantees correctness. CLOSED is a set of already-expanded nodes; once a node is in CLOSED its shortest distance is locked and we skip it if it resurfaces. We also keep a table of best-known g values and a parent pointer per node so we can rebuild the actual path at the end.

Pseudocode

function Dijkstra(graph, start):
    for each node n: g[n] = infinity
    g[start] = 0
    parent[start] = none
    OPEN = priority queue ordered by g   # frontier
    OPEN.push(start, priority = 0)
    CLOSED = empty set                   # visited

    while OPEN is not empty:
        current = OPEN.pop_lowest_g()    # closest unvisited node
        if current in CLOSED: continue
        CLOSED.add(current)              # cost to current is now final

        for each (neighbor, weight) of current:
            new_g = g[current] + weight
            if new_g < g[neighbor]:      # found a cheaper route
                g[neighbor] = new_g
                parent[neighbor] = current
                OPEN.push(neighbor, priority = new_g)

    return g, parent                     # costs + path pointers

At a glance

Complete?Yes — if a node is reachable, Dijkstra will always find a path to it (it explores everything reachable from the start).

Optimal?Yes, with non-negative edge weights — pulling the lowest-g node first guarantees its cost is final and shortest.

TimeO((V + E) log V) with a binary-heap priority queue, where V is nodes and E is edges — each node and edge is processed once, and heap operations cost log V.

SpaceO(V) — you store a cost and parent pointer per node, plus the OPEN frontier and CLOSED set, all bounded by the number of nodes.

👍 When to use it

You need the shortest path in a weighted graph and all weights are non-negative (distances, times, tolls).
You want shortest paths from one source to many or all destinations at once (single-source).
Costs vary between edges, so plain breadth-first search (which assumes equal-cost steps) is not enough.
In AI terms: whenever you'd reach for Uniform-Cost Search — they are the same algorithm.

⚠️ Watch out for

Negative edge weights break it — a later cheap edge can undercut an already-finalized node. Use Bellman-Ford instead.
Do the goal/finalize check when you POP a node from OPEN, not when you push it, or you may lock in a non-shortest cost.
A node can appear in OPEN more than once with different costs; skip it if it's already in CLOSED, and only trust the smallest.
Don't confuse it with A*: Dijkstra uses only g (cost so far). A* adds a heuristic h to aim toward a goal — Dijkstra with h = 0 IS Dijkstra.

Now see it for yourself

Open Dijkstra's Algorithm in the visualizer — step through it, pause, and watch OPEN & CLOSED change.

▶ Watch it run