Paths, Connectivity and Shortest Paths

Main idea

A path is a route along edges, and a graph is connected when you can get from any vertex to any other. When edges have costs, Dijkstra's algorithm finds the cheapest routes by locking in the closest vertex first and working outward, because nothing farther away can offer a cheaper way to reach it.

{\htmlData{sym=0}{d(v)}} = \min_{\htmlData{sym=2}{{u}}}\bigl(d({\htmlData{sym=2}{u}}) + {\htmlData{sym=1}{w(u, v)}}\bigr)

What the symbols mean

$d(v)$
Shortest distance
The cheapest total weight of a path from the start to v.
$w(u, v)$
Edge weight
The cost of the edge from u to v: a length, time or price.
$u$
Neighbor
A vertex with an edge into v; the minimum runs over all of them.

Explanation

A shortest path is simply the cheapest way to get from one dot to another by following the lines, where each line has a cost like distance, time or price. It's what your map app does every time you ask for directions. The formula $d(v) = \min_u \bigl(d(u) + w(u, v)\bigr)$ looks dense, but it's three small pieces: $d(u)$ (the best cost to reach a neighbor $u$ ), $w(u, v)$ (the cost of the last hop from $u$ to $v$ ) and $\min_u$ (try every neighbor and keep the cheapest). In words: the best way to $v$ is the best way to some neighbor, plus one last step. That's all it is.

A walk is any route along edges, and it may repeat vertices. A path is a walk that doesn't, and a cycle is a path that comes back to where it started. If some vertices can't reach each other at all, the graph falls into separate pieces, called connected components.

Unweighted graphs. When every edge costs the same, distance just means "how many hops." Breadth-first search (BFS) finds it by spreading out like a ripple: first the start's neighbors, then their neighbors, and so on, layer by layer. The layer a vertex shows up in is its distance from the start.

Weighted graphs: Dijkstra's algorithm. Once edges have different costs, hop counts lie: two cheap hops can beat one expensive one. Dijkstra's algorithm keeps the ripple idea but spreads out in order of cost instead of hops.

Give the start distance 0 and every other vertex distance $\infty$ .
Settle the unsettled vertex with the smallest distance.
For each of its neighbors, if going through it is cheaper, lower the neighbor's distance.
Repeat until every vertex is settled.

Why is it safe to lock in, or settle, the closest unsettled vertex? Think about any other route to it. That route has to leave the settled region somewhere, and the first unsettled vertex it reaches is already at least as far away as our closest one. With nonnegative weights, the rest of the detour can only add cost. So no detour can beat the distance we have, and it's final. With negative weights that argument falls apart, since a detour could get cheaper as it goes, and other algorithms (Bellman–Ford) are needed.

Notice that this is exactly the equation above at work: every shortest path is built from shortest paths. The best route to $v$ is the best route to some neighbor plus one last edge, and Dijkstra's update step tries each of those last edges. There's an animation further down that runs it on a small graph.

A common mistake. It's tempting to think the first distance a vertex gets is its final one, especially when it comes from a direct edge. It isn't. In the example below, the direct edge from A to B costs 4, but going through C costs only $2 + 1 = 3$ . That's why Dijkstra treats every distance as a guess that can still drop, and only trusts it once the vertex is settled.

See it

Here Dijkstra's algorithm runs from A, and each vertex shows its best known distance so far (? means no route found yet). The ring marks the vertex being settled at each step. Watch the numbers drop: B starts at 4 from the direct edge and falls to 3 once the route through C turns up, and D falls from 10 to 8 by going through B.

Worked examples

Example 1

Edges: A–B weight 4, A–C weight 2, C–B weight 1, B–D weight 5, C–D weight 8. Find the shortest distance from A to D.

1
Start with $d(A) = 0$ and settle A. Its edges give first guesses $d(B) = 4$ and $d(C) = 2$ .

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

In the example graph (A–B 4, A–C 2, C–B 1, B–D 5, C–D 8), what is the shortest distance from A to D?

Problem 2+5 XP

In that graph, which vertex does Dijkstra's algorithm settle right after A?

Problem 3+5 XP

What is the fewest number of edges a connected graph on 10 vertices can have?

Problem 4+5 XP

Breadth-first search finds shortest paths when the edges are:

Problem 5+5 XP

A warehouse robot's map has the aisles S–A (3 s), S–B (1 s), B–A (1 s), A–T (2 s) and B–T (5 s). What is the fastest time from the dock S to the target T, in seconds?

Problem 6+5 XP

A connected graph has 10 vertices and 14 edges. How many edges must be removed, at the least, to leave a spanning tree?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

In a city grid, a courier walks from $(0, 0)$ to $(4, 3)$ using only steps east or north. How many shortest routes avoid the intersection at $(2, 1)$ , which is closed for roadwork?

Where it's used

Navigation apps, internet routers and video game characters run shortest-path searches millions of times a day.

Planning a Robot's Route Through a WarehouseDiscrete · Robotics

Graphs, Degrees and the Handshake Lemma Euler and Hamilton Paths