Step by step
The question
Question: find the shortest path from A to F.
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.
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.
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.
The next row: the new numbers, the rest copied down.
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.
The next row: the new numbers, the rest copied down.
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.
The next row: the new numbers, the rest copied down.
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.
The next row: the new numbers, the rest copied down.
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.
The next row: the new numbers, the rest copied down.
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.
That is the route.
The shortest path is A, B, C, E, D, F, length 9.
10 Check
Add the lengths along the route: 2 + 1 + 3 + 2 + 1 = 9.
Right!
The route with the fewest edges, A, B, D, F, is 10: longer.
Right!
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.