← Home · Shortest path, four ways
Shortest path
Same idea, four ways to study it. Tap a style and find the one that clicks for you. 📺 Prefer to watch? Videos are on the lesson page.
📍 The job: find the smallest total weight from one vertex to another. Small graph? List the paths and add. Big graph? Use Dijkstra (always box the smallest tentative distance).

What it is

In a weighted graph, each edge has a number, a distance, time or cost. The shortest path problem asks: what's the smallest total to get from one vertex to another? It's how a GPS picks your route.

Two methods

1. Inspection (small graphs, 4 to 5 vertices): list every path from start to end, add up the weights, pick the smallest total.

2. Dijkstra's algorithm (bigger graphs): build up the confirmed shortest distance to each vertex, one at a time. The golden rule:

  1. Start vertex = distance 0 (box it). Everything else starts at infinity.
  2. From the just-boxed vertex, update each neighbour: current distance + edge weight, keep it only if it's smaller than what's there.
  3. Box the unboxed vertex with the smallest tentative distance, it's now confirmed.
  4. Repeat until the destination is boxed.

Worked example (inspection)

Edges: A–B (3), A–C (5), B–D (2), C–D (4). Find the shortest path from A to D.

PathAdd the weightsTotal
A → B → D3 + 25
A → C → D5 + 49

Smallest total is 5, so the shortest path is A → B → D, length 5.

Watch out

• Add the weights along the path, don't count the number of edges.
• List every path, the most obvious route isn't always the shortest.
• In Dijkstra, always box the smallest tentative distance next, never skip ahead.
• Once a vertex is boxed, its distance is final, don't change it.

The graph, with the shortest path in gold

A B C D 3 5 2 4 Gold = shortest: A, B, D = 5

The top route (A to B to D) totals 3 + 2 = 5. The bottom route (A to C to D) totals 5 + 4 = 9. Gold wins.

Inspection, at a glance

List → add → pick the smallest.
A,B,D = 5   vs   A,C,D = 9   →   choose 5.

Dijkstra in one image

Box the start at 0, then keep boxing the nearest unboxed vertex. The numbers only ever shrink, and a boxed number never changes.

Warm up first

Don't read yet, just have a go in your head:

What does a "weight" on an edge mean?
A number for that edge, a distance, time, or cost. Shortest path adds these up.
A path is A–B–D with weights 3 and 2. Total?
3 + 2 = 5. Add the weights along the route.
In Dijkstra, which vertex do you box next?
The unboxed one with the smallest tentative distance.

Faded example: A to D, edges A–B(3), A–C(5), B–D(2), C–D(4)

Rung 1 · watch one done fully

A,B,D = 3 + 2 = 5. A,C,D = 5 + 4 = 9. Smallest = A,B,D = 5.

Rung 2 · you fill the gaps

A,B,D = 3 + 2 = ?. A,C,D = 5 + 4 = ?. Shortest = ?

Check my gaps
5, 9, then A,B,D = 5.
Rung 3 · all you

Edges A–B(2), A–C(4), B–C(1), B–D(7), C–D(3). Find the shortest path from A to D. (Hint: there are three routes.) Check below.

Check my answer
A,B,D = 2 + 7 = 9. A,C,D = 4 + 3 = 7. A,B,C,D = 2 + 1 + 3 = 6. Shortest = A,B,C,D = 6, the longer-looking route wins.

Say it back

In one sentence, out loud: how do you find the shortest path on a small graph? If you can say it, you've got it.

⚡ Shortest path, one look

Goalsmallest total weight from start to end
Weightthe number on an edge (distance / time / cost)
Inspectionlist every path → add weights → pick the smallest
Dijkstrabox start at 0, then box the nearest unboxed vertex, repeat
Dijkstra ruleboxed = final, never changes
ExampleA,B,D = 5 beats A,C,D = 9 → shortest is 5
Trapadd weights not edges · the obvious route isn't always shortest