Dijkstra's shortest paths

Earlier you saw that BFS finds shortest paths when every edge counts the same — one step each. But what if edges have weights (a road's length, a toll, a cost)? The fewest-edges path is no longer the cheapest path. Dijkstra's algorithm finds the minimum-weight path from a start node to every other node, as long as the weights are non-negative.

The idea: tentative distances and relaxation

Keep a best-known distance to each node — 0 for the start, infinity for everything else (we haven't reached it yet). These are tentative: they may improve as we discover cheaper routes.

Relaxing an edge u → v (weight w): if dist[u] + w < dist[v], we've found a cheaper way to reach v, so lower dist[v] to dist[u] + w.

Dijkstra repeatedly finalises the unvisited node with the smallest tentative distance, then relaxes its outgoing edges:

dist = { start: 0 }                   // everything else = +infinity
done = {}
while true:
    // pick the unfinished node with the smallest dist (a heap does this fast)
    u = closestUnfinished(dist, done)
    if u is nothing: break            // nothing reachable left
    done[u] = true
    for each edge in graph[u]:        // relax each outgoing edge
        if dist[u] + edge.weight < dist[edge.to]:
            dist[edge.to] = dist[u] + edge.weight

Why non-negative weights matter

When Dijkstra finalises a node, it trusts that its distance can't get any smaller. That's only safe if every other edge adds a non-negative amount — no later detour can reduce a total. Negative edges break this guarantee; for graphs with negative weights you need a different algorithm, Bellman-Ford.

Cost

Selecting the closest node by scanning is O(V²) — fine for small graphs (the next problem does this). Backing the selection with a min-heap / priority queue lowers it to O((V + E) log V), the usual production form. Either way the algorithm is the same: finalise the nearest, relax its edges, repeat.

The next two problems put Dijkstra to work on weighted graphs and tolls.