Practise › Questions › Shortest paths: Dijkstra and Floyd
Shortest paths: Dijkstra and Floyd questions
The cheapest route from one node to another, found by labelling nodes in the order they are settled. A second algorithm does every pair at once, at the cost of a good deal more bookkeeping.
7 original questions · 34 marks · the shortest paths: dijkstra and floyd notes · Decision Mathematics 1
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Describe what the three parts of a Dijkstra label record.
Worked answer
The order in which the vertex was given a permanent label, its final shortest distance from the start, and the working values tried along the way, each crossed out as a smaller one replaces it. B1 B1 B1 for the three parts of the label. The working values carry marks of their own, so they must be shown rather than tidied away.A Dijkstra run gives final labels A 0, B 5, C 7, D 9, E 13, F 15. Given that AC has weight 7, CE weight 6 and EF weight 2, find the shortest route from A to F.
Worked answer
Work back from F. 15 − 13 = 2, the weight of EF, so EF lies on the route. Then 13 − 7 = 6 = CE, and 7 − 0 = 7 = AC. The route is A, C, E, F of length 15. M1 for testing label differences against the edge weights, A1 for the route, B1 for the length 15. Trace the route backwards, testing each edge against the difference of the labels at its ends, rather than reading it off the diagram by eye.A network has edges AB 5, AC 7, AD 9, BC 3, BE 9, CD 3, CE 6, DE 5, DF 10 and EF 2. Use Dijkstra's algorithm to find the shortest route from A to F, showing the order in which the vertices become permanent and every working value.
Worked answer
A is permanent first with 0, and its neighbours take working values B 5, C 7 and D 9.
The smallest is B, permanent 2nd at 5. From B, C would be 5 + 3 = 8, which does not beat 7, and E takes 5 + 9 = 14.
C is permanent 3rd at 7. From C, D would be 7 + 3 = 10, no improvement on 9, and E improves from 14 to 13.
D is permanent 4th at 9. From D, E would be 9 + 5 = 14, no improvement, and F takes 9 + 10 = 19.
E is permanent 5th at 13, and F improves from 19 to 15.
F is permanent 6th at 15. Working back, 15 − 13 = 2 = EF, 13 − 7 = 6 = CE and 7 = AC, so the shortest route is A, C, E, F of length 15.
M1 for the first set of working values, A1 for B and C permanent at 5 and 7, M1 for improving E from 14 to 13, A1 for D permanent at 9, A1 for E permanent at 13, A1 for F permanent at 15, M1 for working the route back, A1 for A, C, E, F. Cross the 14 at E and the 19 at F out rather than erasing them. A correct final answer with a bare set of labels scores about half the marks.For the same network, explain why the route A, D, F is not shortest, and state what Dijkstra did when it examined D.
Worked answer
A, D, F has length 9 + 10 = 19, against 15 for A, C, E, F. When D was made permanent with label 9, F received the working value 19. Later E was made permanent with 13, and 13 + 2 = 15 replaced it. B1 for the length 19, M1 for comparing it with 15, A1 for F taking the working value 19 from D, A1 for 13 + 2 = 15 replacing it. The 19 stays on the diagram crossed out, and it is the evidence that the algorithm was followed rather than the answer guessed.In a Floyd distance matrix the entry from A to E is currently unreachable, A to C is 7 and C to E is 6. State what the C iteration does to both matrices.
Worked answer
It compares the current A to E entry with 7 + 6 = 13. Any finite value beats no route at all, so the distance entry becomes 13 and the route entry for A to E is changed to C, the first vertex to head for. In an undirected network the matrices stay symmetric, so the entry from E to A changes in the same way. M1 for comparing with 7 + 6, A1 for the distance entry 13, A1 for the route entry C, B1 for the matching change from E to A.Explain why Dijkstra's algorithm makes permanent the smallest temporary label anywhere, rather than the cheapest edge from the vertex it has just finished with.
Worked answer
All the weights are non-negative, so the smallest temporary label anywhere cannot be improved by any later route. Reaching that vertex another way would have to pass through a vertex carrying an equal or larger label first. Taking the cheapest edge from the current vertex instead is a greedy walk with no such guarantee, and one short edge into an expensive region can make it go badly wrong. B1 for the weights being non-negative, B1 for no later route improving the smallest label, B1 for the greedy alternative carrying no such guarantee.A network on A, B, C, D has edges AB 3, AC 8, BC 2, BD 5 and CD 6. Write down the initial distance and route matrices, then carry out the first two iterations of Floyd's algorithm, giving both matrices after each one.
Worked answer
Initial distance matrix, rows and columns in the order A, B, C, D, with a dash where there is no edge.
A: −, 3, 8, −
B: 3, −, 2, 5
C: 8, 2, −, 6
D: −, 5, 6, −
In the initial route matrix every entry is its own column label.
A: A, B, C, D
B: A, B, C, D
C: A, B, C, D
D: A, B, C, D
Iteration 1, through A. Compare each entry with the sum of its row's A entry and its column's A entry. B to C would be 3 + 8 = 11 against 2, and every route through A to D is blocked, so nothing changes. Copy both matrices out again.
Iteration 2, through B. A to C becomes 3 + 2 = 5, beating 8, and A to D becomes 3 + 5 = 8, beating no route at all. By symmetry C to A and D to A change with them. The distance matrix is now
A: −, 3, 5, 8
B: 3, −, 2, 5
C: 5, 2, −, 6
D: 8, 5, 6, −
and the route matrix becomes
A: A, B, B, B
B: A, B, C, D
C: B, B, C, D
D: B, B, C, D
B1 for the initial distance matrix, B1 for the initial route matrix, M1 for comparing each entry with the sum through A, A1 A1 for both matrices unchanged, M1 for the comparison through B, A1 for the new distances, A1 for the new route entries, A1 for both matrices written out in full. Write both matrices out after every iteration, including one that changes nothing, since a missing pair costs the marks for that iteration. The route entry records the first vertex on the way, not the last, so A to D reads B and the B row then sends you straight to D.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise shortest paths: dijkstra and floyd one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.