Find the minimum-weight route between two vertices in a weighted network. Useful for minimising travel time, distance, or cost across any connected graph.
🔑 Before this clicks: if any of these feel shaky, a 5-minute refresh makes this page way easier:
In a weighted graph, each edge has a number, a distance, time, or cost. The shortest path problem asks: what's the minimum total weight to get from vertex A to vertex B?
Two methods: for small graphs you can just list all paths and compare. For larger ones, use Dijkstra's algorithm, a systematic step-by-step process that always finds the right answer.
If you only do one thing
Build up the shortest distance to each vertex in turn, and the lowest-total path from start to end falls out.
The 10-minute version
Low energy? Do just this and you have still won the day. Zero is the only fail.
The one move: read the first formula box and the first worked example above, then do Practice Question 1. Screenshot the win for Nat and stop there.
For graphs with 4 to 5 vertices, just list every possible path from start to destination, add up the weights, and take the smallest total.
1
List every path from start (A) to destination (D):
Path 1: A → B → D Path 2: A → C → D
2
Add up the weights for each path:
A, B, D: 3 + 2 = 5
A, C, D: 5 + 4 = 9
3
Choose the minimum: shortest path is A, B, D with total distance 5
2
Method 2, Dijkstra's Algorithm
For larger networks with many possible paths, use Dijkstra's algorithm. It builds up the shortest distances from the start vertex, one confirmed vertex at a time.
Dijkstra's Algorithm, Key Rule
Always "box" (finalise) the unconfirmed vertex with the smallest current tentative distance
1
Set up: Label start vertex with distance 0 (boxed ★). All others start at ∞ (unknown).
2
Update neighbours: For the just-boxed vertex, calculate tentative distances to all unboxed neighbours: (current distance + edge weight). If this is smaller than their existing tentative distance, update it.
3
Box the next vertex: From all unboxed vertices, box the one with the smallest tentative distance. It's now confirmed, this is its true shortest distance.
4
Repeat steps 2 to 3 until the destination is boxed. Its confirmed distance is the answer.
3
Worked Examples
🗺️
Example A · Inspection Method
Find the shortest path from A to D. Edges: A, B(3), A, C(5), B, D(2), C, D(4).
1
List all paths A to D
Path 1: A → B → D Path 2: A → C → D
2
Calculate total weights
A, B, D: 3 + 2 = 5
A, C, D: 5 + 4 = 9
Shortest path: A, B, D, total distance = 5
🧮
Example B · Dijkstra's Algorithm
Find the shortest path from A to E. Edges: A, B(2), A, C(4), B, C(1), B, D(7), C, D(3), C, E(8), D, E(2).
1
Set up, label start vertex
A = 0 (boxed ★) | B, C, D, E = ∞
Dijkstra's table (★ = boxed/finalised):
Step
Process vertex
A
B
C
D
E
Start
,
0
∞
∞
∞
∞
1
Box A (dist 0)
0
2
4
∞
∞
2
Box B (dist 2)
0
2
3
9
∞
3
Box C (dist 3)
0
2
3
6
11
4
Box D (dist 6)
0
2
3
6
8
5
Box E (dist 8) ✓
0
2
3
6
8
2
Trace back the path
E(8) came from D(6+2) ← C(3+3) ← B(2+1) ← A(0+2)
Shortest path: A, B, C, D, E
Shortest path: A, B, C, D, E, total distance = 2+1+3+2 = 8
Dijkstra tip: When multiple vertices tie for smallest tentative distance, you can process either one first. The final answer will be the same, but your table rows may look slightly different.
Practice, tap to reveal answers
1
A network has edges A, B(6), A, C(4), C, D(3), B, D(5). Find the shortest path from A to D using inspection.
Tap to reveal ▾
Path 1: A, B, D = 6 + 5 = 11
Path 2: A, C, D = 4 + 3 = 7 Shortest path: A, C, D, distance = 7
2
Using Dijkstra's on a graph: start vertex P has distance 0. It connects to Q (weight 4) and R (weight 7). After processing P, what are the tentative distances for Q and R?
Tap to reveal ▾
P to Q: 0 + 4 = 4
P to R: 0 + 7 = 7
Next vertex to box: Q (smallest tentative distance = 4)
3
A network has edges A, B(5), A, C(3), B, D(4), C, D(7), B, C(1). Find the shortest path from A to D.
Tap to reveal ▾
Possible paths A to D:
A, B, D: 5 + 4 = 9
A, C, D: 3 + 7 = 10
A, C, B, D: 3 + 1 + 4 = 8
A, B, C, D: 5 + 1 + 7 = 13 Shortest: A, C, B, D, distance = 8
4
What is the key difference between the shortest path and the minimum spanning tree for the same graph?
Tap to reveal ▾
The minimum spanning tree connects ALL vertices using the least total edge weight, it's a tree structure, not a route from one point to another.
The shortest path finds the minimum-weight route between two specific vertices, it doesn't need to visit all vertices, and the same edges may appear in both or neither.
5
In Dijkstra's algorithm, after boxing vertex X with confirmed distance 5, you see X connects to Y with edge weight 3, and Y's current tentative distance is 11. Do you update Y? If so, what is its new tentative distance?
Tap to reveal ▾
New tentative distance via X: 5 + 3 = 8
Current tentative distance of Y: 11
Since 8 < 11 → Yes, update Y to 8
Always update when the new path is shorter than the current tentative distance.