Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture XIII of XIV

Lecture XIII · Data Structures & Algorithms

Graphs: search, shortest paths, spanning trees

Everything in this course so far has been about one structure at a time: a list, a tree, a table, a heap. A graph is different in kind. It is not a container you put things in; it is a way of writing down that some things are related to other things, and almost every interesting problem in computing turns out to be a graph problem wearing a costume.

Two lectures ago we built a priority queue and I promised that Dijkstra’s algorithm and Prim’s algorithm were both just “keep pulling the cheapest thing off a heap until there is nothing left”. This lecture makes good on that. By the end we will have written one search function and gotten breadth-first search, Dijkstra, and Prim out of it by changing a single expression.

The vocabulary, quickly

A graph G=(V,E)G = (V, E) is a set of vertices and a set of edges, where each edge joins two vertices. If the edges have a direction the graph is directed; ours will not be, because a walkway you can only use in one direction is a strange walkway. If the edges carry numbers the graph is weighted, and in this lecture the weight is minutes on foot.

A path is a sequence of vertices each joined to the next by an edge. A cycle is a path that returns to its start. A graph is connected when there is a path between every pair of vertices. The degree of a vertex is how many edges touch it.

One fact worth having in your pocket, because it catches implementation bugs faster than anything else: the degrees of all the vertices sum to 2∣E∣2|E|, since every edge contributes one to each of its two endpoints. That is the handshake lemma, and if your adjacency structure violates it you have added an edge in one direction only.

The ADT, and two ways to build it

As always, the contract before the implementation. A graph should let us:

  • ask for its vertices,
  • ask for the neighbours of a vertex,
  • ask whether a particular edge exists,
  • add vertices and edges.

Now, two implementations. The first is the literal transcription of the definition: keep a set of vertices and a set of edges. It is honest, it is obviously correct, and it is nearly useless, because the operation every algorithm in this lecture performs constantly, “give me the neighbours of vv”, requires scanning every edge in the graph.

The second keeps, for each vertex, a dictionary of its neighbours and the weight to each. Now “give me the neighbours of vv” is one dictionary lookup followed by iterating a structure that already holds exactly the answer.

python runs in your browser · first run downloads ~240 kb
Plate I The same graph, twice. Both classes expose the same four operations, and the last block confirms the handshake lemma: the degrees sum to 20, which is twice the ten edges. The difference is entirely in `nbrs`: the edge-set version filters all ∣E∣|E| edges to answer a question about one vertex, while the adjacency version reads the answer straight out of a dictionary. Everything below assumes the second one.

The cost difference is the whole reason the adjacency representation is universal:

OperationEdge setAdjacency map
addedgeO(1)O(1)O(1)O(1)
hasedge(u, v)O(m)O(m)O(1)O(1)
nbrs(v)O(m)O(m)O(deg⁡v)O(\deg v)
SpaceO(n+m)O(n + m)O(n+m)O(n + m)

with n=∣V∣n = |V| and m=∣E∣m = |E|. Same space, better time, so there is no trade to make. The one case for a third representation, an adjacency matrix, is a dense graph where you want O(1)O(1) hasedge and are happy to pay O(n2)O(n^2) space; road networks and social graphs are nowhere near dense enough for that to pay.

Search: one algorithm, one container, two behaviours

Here is the shape of every graph search ever written:

mark the start as reached
put the start in the frontier
while the frontier is not empty:
    take some vertex v out of the frontier
    for each neighbour u of v that is not yet reached:
        mark u as reached
        remember that we reached u from v
        put u in the frontier

The word doing all the work is some. Which vertex you take out of the frontier is the entire algorithm. Take the oldest and you get breadth-first search. Take the newest and you get depth-first search. That is not an analogy; it is one character of difference in the code.

BFS explores in rings: everything one hop from the start, then everything two hops away, and so on. Because of that, the first time BFS reaches a vertex it has reached it by a path with the fewest possible edges. DFS charges as deep as it can down one branch before backing up, and offers no such guarantee.

python runs in your browser · first run downloads ~240 kb
Plate II Queue against stack, on the same graph from the same start. The two functions are identical except for `frontier.pop(0)` and `frontier.pop()`, which is to say except for which end of the list the next vertex comes out of, and that one character sends them through the campus in completely different orders. Both take the direct one-hop edge to Ted's, since one hop is the fewest hops there are, and both therefore pay twenty minutes for a walk that can be done in fourteen. Read the Gampel row for the sharper version: identical hop counts, 25 minutes against 9. Neither search is minimising time, and that is the gap the next section closes.

Recursive DFS, and a warning

DFS has a natural recursive form, since “go as deep as you can then back up” is what the call stack does for free:

def dfs(G, v, tree=None):
    if tree is None:
        tree = {v: None}
    for u, w in G.nbrs(v):
        if u not in tree:
            tree[u] = v
            dfs(G, u, tree)
    return tree

Elegant, and a genuine trap. As Lecture VI established, Python’s recursion limit is about a thousand frames, and a graph with a long path will blow through it. A road network laid end to end is exactly such a graph. The iterative version with an explicit stack has no such limit, which is why the plate above uses it. This is the same lesson as the call-stack lecture, arriving from a new direction: recursion is a control structure with a memory cost, and the explicit stack is always available when the cost is too high.

Weights change the question

Now the point of the whole lecture. BFS finds the path with the fewest edges. On a weighted graph that is very often the wrong answer, because three short walkways can beat one long one.

Dijkstra’s algorithm fixes this by settling vertices in order of total distance from the start rather than in order of hop count. It keeps a tentative distance for every vertex, starts them all at infinity except the source, and repeats:

  1. Among the vertices not yet settled, take the one with the smallest tentative distance, and settle it: declare its distance final.
  2. Relax each of its edges: for each neighbour uu, if going through vv beats uu‘s current tentative distance, lower it and record vv as uu‘s parent.

The claim that makes it work is that step 1 is safe: when you settle vv, its tentative distance really is the true shortest distance. Suppose it were not, and some shorter path to vv existed. That path has to leave the settled set at some point, at some vertex xx that is not yet settled. But everything on the path up to xx is non-negative, so the distance to xx is at most the length of the whole path, which we assumed is less than vv‘s tentative distance. Then xx would have had a smaller tentative distance than vv, and step 1 would have chosen xx instead. Contradiction.

Notice exactly where that argument used non-negativity, and notice that it is load-bearing: Dijkstra is wrong on graphs with negative edge weights, not slow, wrong. It will settle a vertex, declare it final, and then later discover a cheaper route it can no longer use. Walking times are never negative, so we are safe here.

python runs in your browser · first run downloads ~240 kb
Plate III Dijkstra, settling vertices cheapest-first, with the settle order printed as it happens. This is deliberately the O(n2)O(n^2) version that scans for the minimum by hand rather than using a heap, because the scan is what a priority queue replaces and it is worth seeing the thing being replaced. Compare the route to Ted's against Plate II: BFS returned a path with fewer hops and more minutes. Both are correct answers to different questions.

Where the heap goes

That linear scan for the cheapest unsettled vertex costs O(n)O(n) and runs nn times, so Dijkstra as written is O(n2)O(n^2). Every step of it is a removemin, and Lecture XII built the structure that does removemin in O(log⁡n)O(\log n).

Dropping a heap in gives O(mlog⁡n)O(m \log n), and the standard implementation does not even bother with changepriority. Instead it pushes a new entry every time a distance improves and ignores entries for vertices already settled when they surface. That is the lazy heap, and it trades a little memory (the heap can hold more than nn items) for not needing the index map that Lecture XII’s changepriority required.

python runs in your browser · first run downloads ~240 kb
Plate IV Dijkstra on a real binary heap, using the standard library's `heapq`, and counting the waste. The lazy strategy pushes a fresh entry on every improvement rather than updating an existing one, so some pops surface a vertex that is already settled; the plate counts those stale pops explicitly. On ten edges the heap is slower than the scan it replaces, which is worth saying plainly: O(mlog⁡n)O(m \log n) beats O(n2)O(n^2) asymptotically and loses on small inputs, exactly as Lecture III would predict.

Spanning trees, and the one-word difference

A spanning tree of a connected graph is a subset of edges that keeps everything connected and contains no cycle. It always has exactly n−1n - 1 edges. A minimum spanning tree is one whose total weight is as small as possible: the cheapest way to wire the whole campus so every building is reachable, with no redundant cable.

Prim’s algorithm builds one. Start anywhere, and repeatedly add the cheapest edge that joins a vertex already in the tree to a vertex not yet in it.

Now look at that next to Dijkstra and notice how nearly identical they are. Both maintain a set of settled vertices, both repeatedly take the cheapest thing outside it, both relax edges. The only difference is what “cheapest” means:

  • Dijkstra scores a neighbour uu by dist(v)+w(v,u)\text{dist}(v) + w(v, u): how far uu is from the start.
  • Prim scores it by w(v,u)w(v, u) alone: how far uu is from the tree.

One term dropped. That is the entire difference between a shortest-path tree and a minimum spanning tree, and it is why Lecture XII could promise you both for the price of one heap.

python runs in your browser · first run downloads ~240 kb
Plate V The unification, in code. A single `priority_first_search` takes a `key` function that scores a neighbour, and BFS, Dijkstra and Prim are three one-line arguments to it: d+1d + 1, d+wd + w, and ww. The settle orders and the resulting tree weights differ; the search does not. This is Sheehy's framing and it is the most useful single idea in the chapter: once you see the three as one, you stop memorising three algorithms and start remembering one algorithm and three questions.

The plate: the campus, and four ways across it

The figure this lecture exists for. The graph below is the UConn Storrs campus, and none of it is invented: the twenty-five landmarks sit at their real OpenStreetMap coordinates, and each of the forty-six edge weights is the true shortest walking distance between two landmarks along the actual footway network, converted to minutes at a stated 1.35 metres per second. When the plate says a walk takes nine minutes, that is a measurement.

The route to try first is Gampel to the Dairy Bar. Run BFS: five hops, and nearly thirty-six minutes on your feet. Now run Dijkstra: seven hops, and just over twenty. BFS wins the count it is optimising and loses you a quarter of an hour, which is the whole lecture in one gesture.

Then run McHugh to Ted’s, where the two return exactly the same route, three hops and 10.1 minutes, and ask why. There is no long detour edge anywhere between those two, so the path with the fewest walkways happens also to be the path with the fewest minutes. The disagreement between BFS and Dijkstra is a property of the map, not of the algorithms: it appears when a graph offers a short-in-hops route that is long in weight, and vanishes when it does not. Over all 600 ordered pairs of landmarks on this campus the two return different routes for 231 of them, so most pairs are worth trying and a good few are not.

Then switch to Prim, which ignores your start and goal entirely and wires the whole campus instead, and watch a different shape of answer come out of nearly the same code.

1.01.01.11.41.51.81.91.91.91.92.12.42.52.53.33.33.64.04.04.14.14.14.54.55.15.15.45.45.55.65.65.65.85.85.96.06.06.06.36.76.87.28.58.68.89.8Hilltop12.8Northwest15.8Ted's15.3Putnam6.8Jorgensen10.2Gant12.3Towers18.6Gampel0.0Union6.6McHugh5.6Gentry8.9Bookstore1.4Rec Center1.9ITE3.7Babbidge3.8Storrs Hall11.4Wilbur Cross11.4Monteith7.8Arjona7.9Mirror Lake11.8Dairy Bar20.1Young17.7Rome Commons7.0Buckley13.7Kathmandu18.8200 mthe Hilltop Community Centerthe Northwest Dining HallTed's Restaurant and Barthe Israel Putnam Refectorythe Jorgensen Centerthe Gant South Buildingthe Towers Student CenterGampel Pavilionthe Student UnionMcHugh Hallthe Gentry Buildingthe UConn Bookstorethe Student Recreation Centerthe ITE buildingthe Homer D. Babbidge LibraryAugustus Storrs Hallthe Wilbur Cross Buildingthe Monteith Buildingthe Arjona BuildingMirror Lakethe UConn Dairy Barthe Wilfred B. Young BuildingRome Commons on South CampusBuckley Residence HallKathmandu Kitchen
Breadth-first search, depth-first search, Dijkstra and Prim run over the same campus graph from Gampel Pavilion to Kathmandu Kitchen: hops, walking minutes, and landmarks settled. Each route's minutes are marked fits or over against a stated 15-minute passing period; Prim spans the campus rather than walking a route, so its total is left unmarked.
algorithmhopsminutes · vs 15settled
BFS · fewest hops522.4 over25
DFS · any route at all1984.1 over25
Dijkstra · fewest minutes518.8 over24
Prim · spanning tree24 walkways82.325

Against a stated 15-minute passing period (an assumption of this figure, not a rule of anyone's registrar): even the fastest route is 18.8 minutes, 3.8 over, so this walk does not fit and no search will make it. Across the map, 218 of the 300 pairs of landmarks fit, 39 of them only if you walk the fastest route rather than the one with the fewest walkways, and the longest of them is the Hilltop Community Center to Kathmandu Kitchen, 31.6 minutes apart over 7 hops even by the fastest route, so no period shorter than that gets every pair on this campus to class.

All four searches, run at build time from Gampel Pavilion to Kathmandu Kitchen. They disagree here. Breadth first takes 5 hops and 22.4 minutes; Dijkstra takes 5 hops and 18.8. Same hop count, 3.6 extra minutes: breadth first is indifferent between routes of equal length, and picks wrong. The two landmarks are 1082 m apart in a straight line, and no walkway on this campus goes in a straight line. With JavaScript enabled the map is clickable, the route is yours to choose, and every algorithm steps one settled building or one relaxed walkway at a time.

Route
A click on the map sets
Algorithm
Passing period, assumed
Trace

settled, darker earlier frontier: seen, not settled the route, or Prim's tree the walkway being examined the small green number by a landmark is its current key: hops for BFS, minutes for Dijkstra, the cheapest single walkway into it for Prim

25 landmarks and 46 walkways, all of them real: coordinates from OpenStreetMap (© OpenStreetMap contributors, ODbL 1.0, pulled 2026-07-27), weights measured as shortest paths along the OSM footway network and converted at 1.35 m/s. Each edge is drawn as a straight chord between two buildings, so the line is a simplification and only the number is the measurement. Total walking on the map: 205.9 minutes over 16710 m.

Plate VI Search over the real campus: 25 landmarks at their true OpenStreetMap coordinates, 46 walkways weighted by the measured shortest distance along the real footway network. Pick a start and a goal, or take one of the three presets (McHugh to Ted's, Gampel to the Kathmandu restaurant, Gampel to the Dairy Bar), choose an algorithm, then Step to advance one settled vertex or relaxed edge at a time, or Run. Settled vertices shade in the order they were settled, the frontier is outlined in ochre, and the answer is drawn in green. BFS and Dijkstra report both hops and minutes so the disagreement between them is visible rather than asserted. Prim ignores the endpoints and spans everything. Every walking time is then marked fits or over against an assumed passing period, 15 minutes until you move the control: that threshold is a premise of the figure and not a rule of the university, which is why it is a knob and not a caption. 218 of the 300 unordered pairs of landmarks fit inside it, 39 of them only if you walk Dijkstra's route rather than BFS's, and the two furthest apart on this campus, the Hilltop Community Center and Kathmandu Kitchen, are 31.6 minutes apart by the fastest walk that exists. There is deliberately no A* here; the heuristic search is a separate figure in a separate lecture, and the point of this one is that these four are the same algorithm.

What it costs

With nn vertices and mm edges, on the adjacency representation:

AlgorithmTimeAnswers
BFSO(n+m)O(n + m)fewest edges from one source
DFSO(n+m)O(n + m)reachability, cycles, topological order
Dijkstra, linear scanO(n2)O(n^2)cheapest total weight from one source
Dijkstra, binary heapO(mlog⁡n)O(m \log n)the same
Prim, binary heapO(mlog⁡n)O(m \log n)minimum spanning tree

Every one of them visits each vertex once and each edge a constant number of times; the log⁡n\log n factors are the heap, not the graph. Note that BFS and DFS are linear in the size of the graph, which is as good as it can possibly get: you cannot answer a question about a graph without at least looking at it.

The row worth arguing about is the two Dijkstras. O(mlog⁡n)O(m \log n) beats O(n2)O(n^2) when the graph is sparse, meaning mm is closer to nn than to n2n^2, and real graphs almost always are: a building does not have a walkway to every other building. On a dense graph the scan version can win. Lecture III’s whole point was that asymptotics are a claim about growth and not about any particular input, and this is the payoff.

Where you meet this again

Almost everywhere, once you learn to see it. Dependency resolution in a package manager is a topological sort, which is DFS. Word ladders and puzzle states are BFS. Network routing is Dijkstra. Clustering by “cut the most expensive edges of the MST” is Prim. Garbage collection is reachability from a root set. The next lecture takes the spanning-tree half of this one and rebuilds it around a different data structure, the disjoint-set forest, which yields Kruskal’s algorithm and one of the most surprising running times in the subject.

Problems

Work these in order. The last two run their own checks; make every row green.

  1. On paper, the handshake. Prove that the sum of all vertex degrees equals 2∣E∣2|E| in an undirected graph, and use it to prove that the number of vertices of odd degree is always even. Then apply it: someone tells you they have built a graph of 7 vertices in which every vertex has degree 3. Without drawing anything, say why they are wrong.

  2. On paper, the negative edge. Construct the smallest graph you can, with at most four vertices and one negative edge weight, on which Dijkstra returns a wrong answer. Show the settle order, show the wrong distance it reports, and show the true shortest path. Then identify the exact sentence in this lecture’s correctness argument that fails on your example.

  3. On paper, the difference. Take the campus graph from Plate V. Run Dijkstra from McHugh and write down the tree it produces; run Prim from McHugh and write down that tree. They are different. Now answer the real question: is Prim’s tree ever a shortest-path tree? Give a two-vertex-plus-one condition under which they coincide, or give a graph where they cannot, and say which of the two you found easier and why.

  4. Breadth-first paths. Write bfs_paths(G, start), returning a dictionary from each reachable vertex to the actual shortest path (as a list of vertices) from start. Unreachable vertices must be absent from the dictionary entirely, not present with a value of None. The checks verify hop counts, verify that every path returned is a genuine walk in the graph, and pin the tie-break that sorted neighbours force.

    The checks · run against your code

    paths = bfs_paths(G, "A")
    # the start is its own path
    assert paths["A"] == ["A"]
    # every vertex is reachable in this graph
    assert sorted(paths.keys()) == ["A", "B", "C", "D", "E", "F", "G"]
    # hop counts are the true minimum
    assert len(paths["B"]) - 1 == 1
    assert len(paths["D"]) - 1 == 2
    assert len(paths["G"]) - 1 == 3
    # every returned path is a real walk in the graph
    for v, p in paths.items():
        assert p[0] == "A" and p[-1] == v
        for i in range(len(p) - 1):
            assert p[i + 1] in dict(G.nbrs(p[i]))
    # with sorted neighbours, D is reached via B and not via C
    assert paths["D"] == ["A", "B", "D"]
    # an isolated vertex is simply absent, not mapped to None
    G2 = Graph([("A", "B", 1)])
    G2._nbrs.setdefault("Z", {})
    p2 = bfs_paths(G2, "A")
    assert "Z" not in p2
    assert sorted(p2.keys()) == ["A", "B"]
    python runs in your browser · first run downloads ~240 kb
    Plate VII Paths, not just distances. Eight checks: the trivial path to the start, full reachability, three exact hop counts, a structural check that walks every returned path edge by edge through the graph, the tie-break at D, and the isolated-vertex case. That last one is the one that catches a `dict` initialised with every vertex up front.
    Hint one

    Keep the frontier as a list used as a queue, with pop(0) to remove. Store the paths directly: when you reach u from v, set paths[u] = paths[v] + [u]. That copies a list per vertex, which is wasteful but correct and readable; the parent-pointer version in the lecture is the efficient one.

    Hint two

    The isolated-vertex check is the one that fails if you write paths = {v: None for v in G.vertices()} at the top. Start the dictionary with only the start vertex in it, and let it grow as you reach things. Membership in the dictionary is your “have I reached this?” mark, so you do not need a separate visited set at all.

    The solution

    The queue, with the path carried along instead of reconstructed:

    def bfs_paths(G, start):
      paths = {start: [start]}
      frontier = [start]
      while frontier:
          v = frontier.pop(0)
          for u, w in G.nbrs(v):
              if u not in paths:
                  paths[u] = paths[v] + [u]
                  frontier.append(u)
      return paths

    Seven lines, and the subtle one is if u not in paths, which does double duty as the reached-test and as the thing that makes the dictionary contain exactly the reachable vertices. Mark on enqueue, not on dequeue: if you move the marking down to where v comes out of the queue, a vertex with two neighbours already in the frontier will be enqueued twice, and while the answer stays correct the frontier can grow to O(m)O(m) rather than O(n)O(n).

  5. Dijkstra, for real. Write dijkstra(G, start) returning (dist, tree). Settle vertices cheapest-first; a settled vertex is final and must never be relaxed again. Unreachable vertices keep a distance of INF. The checks are built around a graph where the direct edge is deliberately not the cheapest route, so an implementation that just reads off adjacent weights fails immediately. The last structural check verifies the triangle inequality across every edge, which is the real certificate that a distance labelling is optimal.

    The checks · run against your code

    dist, tree = dijkstra(G, "A")
    # the direct edge is not always the cheapest route
    assert dist["C"] == 1
    assert dist["B"] == 3          # A -> C -> B costs 3, the direct A -> B costs 4
    assert tree["B"] == "C"
    # and the effect compounds downstream
    assert dist["D"] == 8          # A -> C -> B -> D
    assert dist["E"] == 11         # A -> C -> B -> D -> E
    assert dist["F"] == 13         # the long way round beats the direct C -> F of 15
    # start is zero and has no parent
    assert dist["A"] == 0
    assert tree["A"] is None
    # every distance is consistent with its parent edge
    for v in dist:
        if tree[v] is not None:
            w = dict(G.nbrs(v))[tree[v]]
            assert abs(dist[v] - (dist[tree[v]] + w)) < 1e-9
    # the triangle inequality holds across EVERY edge, which is the real
    # certificate that these distances are optimal
    for u in G.vertices():
        for v, w in G.nbrs(u):
            assert dist[v] <= dist[u] + w + 1e-9
    # an unreachable vertex keeps distance infinity
    G2 = Graph([("A", "B", 1)])
    G2._nbrs.setdefault("Z", {})
    d2, t2 = dijkstra(G2, "A")
    assert d2["Z"] == INF
    python runs in your browser · first run downloads ~240 kb
    Plate VIII Shortest paths, graded. The graph is rigged: A to B directly costs 4, but A to C to B costs 3, and that saving propagates all the way down to E and F. Beyond the exact distances, two structural checks matter more than the numbers: every distance must equal its parent's distance plus the connecting edge, and no edge anywhere may violate d[v]≤d[u]+w(u,v)d[v] \le d[u] + w(u,v). Any labelling passing both is optimal, whatever route you took to find it.
    Hint one

    Three structures: dist starting at INF for everything except start, tree starting as &#123;start: None&#125;, and a done set. Loop until done holds every vertex, or until the cheapest unsettled vertex has distance INF, which means the rest is unreachable and you must stop rather than loop forever.

    Hint two

    Finding the cheapest unsettled vertex is a plain scan over dist skipping anything in done. When you relax, guard with both u not in done and the improvement test dist[v] + w &lt; dist[u]; set tree[u] = v in the same branch that lowers dist[u], never outside it, or the tree will disagree with the distances.

    The solution

    Settle, then relax, with the unreachable case handled explicitly:

    def dijkstra(G, start):
      dist = {v: INF for v in G.vertices()}
      tree = {start: None}
      dist[start] = 0
      done = set()
      while len(done) < len(dist):
          v = None
          for u in dist:
              if u not in done and (v is None or dist[u] < dist[v]):
                  v = u
          if dist[v] == INF:
              break
          done.add(v)
          for u, w in G.nbrs(v):
              if u not in done and dist[v] + w < dist[u]:
                  dist[u] = dist[v] + w
                  tree[u] = v
      return dist, tree

    The if dist[v] == INF: break is not an optimisation, it is correctness: without it, a graph with an unreachable component settles a vertex at infinite distance and then relaxes INF + w into its neighbours, which in floating point is still INF and merely wastes time, but in an integer-weighted implementation would overflow. Note also that the entire body of the loop is one removemin followed by one pass over nbrs(v), which is exactly the shape that swapping in a heap improves, and exactly the shape that Prim shares.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.