Worked examples
The question
Question: find the shortest path from A to D.
from A to D: AB 2, AC 5, BC 1, BD 6, CD 2
1 Draw the graph
The numbers on the edges are lengths: how far it is along each edge.
2 Start the table
A table: a column for each vertex.
Each cell holds how far it is from A so far, and, small, the vertex we came from.
A is 0 from itself.
0
The others are not reached yet: ∞, as far as can be.
∞
∞
∞
Careful!
Fewer edges is not the same as shorter.
We must add the lengths.
Careful: not A, B, D = 2 + 6 = 8 ✗
3 Round 1
The smallest open number is A: 0.
Nothing can beat it any more, so A is final.
B: 0 plus 2 is 2.
C: 0 plus 5 is 5.
from A: B: 0 + 2 = 2, C: 0 + 5 = 5
The next row: the new numbers, the rest copied down.
0
2A
5A
∞
4 Round 2
The smallest open number is B: 2.
Nothing can beat it any more, so B is final.
C: 2 plus 1 is 3, less than 5.
Change it.
D: 2 plus 6 is 8.
from B: C: 2 + 1 = 3 < 5, D: 2 + 6 = 8
The next row: the new numbers, the rest copied down.
–
2A
3B
8B
5 Round 3
The smallest open number is C: 3.
Nothing can beat it any more, so C is final.
D: 3 plus 2 is 5, less than 8.
Change it.
from C: D: 3 + 2 = 5 < 8
The next row: the new numbers, the rest copied down.
–
–
3B
5C
6 Round 4
The smallest open number is D: 5.
Nothing can beat it any more, so D is final.
7 The route back
Go back with the small letters: D from C, C from B, B from A.
D from C, C from B, B from A
That is the route.
The shortest path is A, B, C, D, length 5.
= A, B, C, D: length 5
8 Check
Add the lengths along the route: 2 + 1 + 2 = 5.
Right!
2 + 1 + 2 = 5
The route with the fewest edges, A, B, D, is 8: longer.
Right!
fewest edges A, B, D: 2 + 6 = 8 > 5
Let's look back.
First: draw the graph.
Then: start the table.
Then: round 1.
Then: round 2.
Then: round 3.
Then: round 4.
Then: the route back.
Last: check.
Answer = A, B, C, D: length 5
▶ Watch it solved
The question
Question: find the shortest path from A to E.
from A to E: AB 4, AC 2, BC 1, BD 5, CD 8, CE 10, DE 2
1 Draw the graph
The numbers on the edges are lengths: how far it is along each edge.
2 Start the table
A table: a column for each vertex.
Each cell holds how far it is from A so far, and, small, the vertex we came from.
A is 0 from itself.
0
The others are not reached yet: ∞, as far as can be.
∞
∞
∞
∞
Careful!
Fewer edges is not the same as shorter.
We must add the lengths.
Careful: not A, C, E = 2 + 10 = 12 ✗
3 Round 1
The smallest open number is A: 0.
Nothing can beat it any more, so A is final.
B: 0 plus 4 is 4.
C: 0 plus 2 is 2.
from A: B: 0 + 4 = 4, C: 0 + 2 = 2
The next row: the new numbers, the rest copied down.
0
4A
2A
∞
∞
4 Round 2
The smallest open number is C: 2.
Nothing can beat it any more, so C is final.
B: 2 plus 1 is 3, less than 4.
Change it.
D: 2 plus 8 is 10.
E: 2 plus 10 is 12.
from C: B: 2 + 1 = 3 < 4, D: 2 + 8 = 10, E: 2 + 10 = 12
The next row: the new numbers, the rest copied down.
–
3C
2A
10C
12C
5 Round 3
The smallest open number is B: 3.
Nothing can beat it any more, so B is final.
D: 3 plus 5 is 8, less than 10.
Change it.
from B: D: 3 + 5 = 8 < 10
The next row: the new numbers, the rest copied down.
–
3C
–
8B
12C
6 Round 4
The smallest open number is D: 8.
Nothing can beat it any more, so D is final.
E: 8 plus 2 is 10, less than 12.
Change it.
from D: E: 8 + 2 = 10 < 12
The next row: the new numbers, the rest copied down.
–
–
–
8B
10D
7 Round 5
The smallest open number is E: 10.
Nothing can beat it any more, so E is final.
8 The route back
Go back with the small letters: E from D, D from B, B from C, C from A.
E from D, D from B, B from C, C from A
That is the route.
The shortest path is A, C, B, D, E, length 10.
= A, C, B, D, E: length 10
9 Check
Add the lengths along the route: 2 + 1 + 5 + 2 = 10.
Right!
2 + 1 + 5 + 2 = 10
The route with the fewest edges, A, C, E, is 12: longer.
Right!
fewest edges A, C, E: 2 + 10 = 12 > 10
Let's look back.
First: draw the graph.
Then: start the table.
Then: round 1.
Then: round 2.
Then: round 3.
Then: round 4.
Then: round 5.
Then: the route back.
Last: check.
Answer = A, C, B, D, E: length 10
▶ Watch it solved
The question
Question: find the shortest path from A to F.
from A to F: AB 2, AC 4, BC 1, BD 7, CE 3, DF 1, DE 2, EF 5
1 Draw the graph
The numbers on the edges are lengths: how far it is along each edge.
2 Start the table
A table: a column for each vertex.
Each cell holds how far it is from A so far, and, small, the vertex we came from.
A is 0 from itself.
0
The others are not reached yet: ∞, as far as can be.
∞
∞
∞
∞
∞
Careful!
Fewer edges is not the same as shorter.
We must add the lengths.
Careful: not A, B, D, F = 2 + 7 + 1 = 10 ✗
3 Round 1
The smallest open number is A: 0.
Nothing can beat it any more, so A is final.
B: 0 plus 2 is 2.
C: 0 plus 4 is 4.
from A: B: 0 + 2 = 2, C: 0 + 4 = 4
The next row: the new numbers, the rest copied down.
0
2A
4A
∞
∞
∞
4 Round 2
The smallest open number is B: 2.
Nothing can beat it any more, so B is final.
C: 2 plus 1 is 3, less than 4.
Change it.
D: 2 plus 7 is 9.
from B: C: 2 + 1 = 3 < 4, D: 2 + 7 = 9
The next row: the new numbers, the rest copied down.
–
2A
3B
9B
∞
∞
5 Round 3
The smallest open number is C: 3.
Nothing can beat it any more, so C is final.
E: 3 plus 3 is 6.
from C: E: 3 + 3 = 6
The next row: the new numbers, the rest copied down.
–
–
3B
9B
6C
∞
6 Round 4
The smallest open number is E: 6.
Nothing can beat it any more, so E is final.
D: 6 plus 2 is 8, less than 9.
Change it.
F: 6 plus 5 is 11.
from E: D: 6 + 2 = 8 < 9, F: 6 + 5 = 11
The next row: the new numbers, the rest copied down.
–
–
–
8E
6C
11E
7 Round 5
The smallest open number is D: 8.
Nothing can beat it any more, so D is final.
F: 8 plus 1 is 9, less than 11.
Change it.
from D: F: 8 + 1 = 9 < 11
The next row: the new numbers, the rest copied down.
–
–
–
8E
–
9D
8 Round 6
The smallest open number is F: 9.
Nothing can beat it any more, so F is final.
9 The route back
Go back with the small letters: F from D, D from E, E from C, C from B, B from A.
F from D, D from E, E from C, C from B, B from A
That is the route.
The shortest path is A, B, C, E, D, F, length 9.
= A, B, C, E, D, F: length 9
10 Check
Add the lengths along the route: 2 + 1 + 3 + 2 + 1 = 9.
Right!
2 + 1 + 3 + 2 + 1 = 9
The route with the fewest edges, A, B, D, F, is 10: longer.
Right!
fewest edges A, B, D, F: 2 + 7 + 1 = 10 > 9
Let's look back.
First: draw the graph.
Then: start the table.
Then: round 1.
Then: round 2.
Then: round 3.
Then: round 4.
Then: round 5.
Then: round 6.
Then: the route back.
Last: check.
Answer = A, B, C, E, D, F: length 9
▶ Watch it solved
