Questions on shortest paths: Dijkstra and Floyd

Question 1

Describe what the three parts of a Dijkstra label record.

Accepted 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 must be shown rather than tidied away.

Question 2

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.

Accepted 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.

Question 3

The implementation of Dijkstra's algorithm used here has quadratic order. A run on a network of 40 vertices takes 0.08 seconds. Estimate the time a run on 200 vertices would take.

Accepted Answer

Quadratic order means the work grows with the square of the number of vertices, so five times as many vertices multiplies the work by 5² = 25. M1 for squaring the ratio of the sizes.
The estimate is 0.08 × 25 = 2.0 seconds. A1.
Treat the answer as an estimate: the order ignores the constant multiplier and the lower-order terms, so a real run may differ while still growing in this way.

Question 4

A network has edges PQ 6, PR 9, QR 4, QS 9, RS 5, ST 3 and RT 12, and a Dijkstra run from P gives the final labels P 0, Q 6, R 9, S 14, T 17. Find the shortest route from P to T.

Accepted Answer

Work back from T, testing each edge at the vertex you stand on against the difference of the labels at its ends.
17 − 14 = 3, the weight of ST, so ST lies on the route. 14 − 9 = 5, the weight of RS, so RS does too; note that 14 − 6 = 8 while QS weighs 9, so QS does not. 9 − 0 = 9, the weight of PR, so PR completes it. M1 for testing label differences against edge weights.
The route is P, R, S, T. A1. Its length is the label at T, 17. B1.
Testing every edge at the vertex reached is what makes the answer safe: here two edges arrive at S and only one of them passes the test, so the route is unique. Where more than one passes, more than one shortest route exists.

Question 5

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.

Accepted 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.

Question 6

For the same network, explain why the route A, D, F is not shortest, and state what Dijkstra did when it examined D.

Accepted 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.

Question 7

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, both along direct edges. State what the C iteration does to both matrices.

Accepted 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.

Question 8

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.

Accepted 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.

Question 9

A network has edges PQ 4, PR 7, QR 2, QS 9, RS 6, RT 8, ST 3, SU 5 and TU 4. Use Dijkstra's algorithm to find the shortest route from P to U, showing the order in which the vertices become permanent and every working value.

Accepted Answer

P is permanent 1st at 0, and its neighbours take working values Q 4 and R 7. M1 for the first working values. The smallest is Q, permanent 2nd at 4. From Q, R improves from 7 to 6 and S takes 4 + 9 = 13. A1 for Q and R at 4 and 6. R is permanent 3rd at 6. From R, S improves from 13 to 12 and T takes 6 + 8 = 14. A1 for S at 12 with the 13 replaced. S is permanent 4th at 12. From S, T would be 12 + 3 = 15, no improvement on 14, and U takes 12 + 5 = 17. T is permanent 5th at 14. From T, U would be 14 + 4 = 18, no improvement on 17. U is permanent 6th at 17. A1 for T at 14 and U at 17. Working back: 17 − 12 = 5 = SU, 12 − 6 = 6 = RS, 6 − 4 = 2 = QR and 4 = PQ, so the shortest route is P, Q, R, S, U of length 17. A1. Cross the 7 at R and the 13 at S out rather than erasing them. The route reaches R through Q even though PR is a direct edge, which is exactly what the crossed-out 7 records.

Question 10

A completed Floyd route matrix on P, Q, R, S, T has row P reading P, Q, Q, Q, T; row Q reading P, Q, R, R, T; row R reading Q, Q, R, S, S; row S reading R, R, R, S, T; and row T reading P, Q, S, S, T. Use it to write down the shortest route from P to S and the shortest route from T to R, explaining each step.

Accepted Answer

Each entry names the first vertex to head for on the way from its row to its column, so the route is read one hop at a time.
P to S: the entry in row P, column S is Q, so go to Q. In row Q, column S the entry is R, so go to R. In row R, column S the entry is S itself, so the next step arrives. The route is P, Q, R, S. M1 for reading the first vertex off the row, A1 for the route.
T to R: row T, column R gives S, so go to S. Row S, column R gives R itself, so the next step arrives. The route is T, S, R. M1 for the second route, A1 for T, S, R.
The entry names the first vertex on the way, not the last, so the row changes at every step while the column never does. Reading down the column instead traces the route backwards, and gives a different answer wherever the network is directed.

Question 11

A network has edges PQ 5, PR 3, QR 3, QT 6, RS 4, ST 7, QS 8 and RT 9. Find the shortest route from P to T that passes through S, and compare its length with the shortest route from P to T with no such requirement.

Accepted Answer

A route through S is a route from P to S followed by a route from S to T, and each part may be made as short as possible on its own. M1 for splitting the problem in two.
P to S: P, R, S costs 3 + 4 = 7, against P, Q, S at 13 and P, R, Q, S at 14. A1 for P, R, S of length 7.
S to T: the direct edge costs 7, against S, R, T at 13 and S, Q, T at 14.
So the shortest route through S is P, R, S, T, of length 7 + 7 = 14. A1.
With no such requirement, Dijkstra from P gives labels P 0, R 3, Q 5, S 7, T 11, and the shortest route is P, Q, T of length 11. B1.
Requiring S costs 3 more.

Question 12

The network shows eleven roads joining seven junctions, with the length of each road in kilometres marked on it. Use Dijkstra's algorithm on the network to find the shortest route from A to G, showing the order in which the junctions become permanent and every working value you write down, and state the length of that route.

Accepted Answer

A is permanent 1st at 0, and its two neighbours take the working values B 4 and C 6. M1 for the first working values, taken off the network.
B is the smallest, permanent 2nd at 4. From B, C would be 4 + 3 = 7, which does not beat 6; D takes 4 + 7 = 11 and E takes 4 + 9 = 13.
C is permanent 3rd at 6. From C, D would be 6 + 5 = 11, equal to the 11 already there, so nothing changes; F takes 6 + 12 = 18. A1 for B and C permanent at 4 and 6.
D is permanent 4th at 11. From D, E would be 11 + 4 = 15, no improvement on 13, but F improves from 18 to 17. M1 for crossing the 18 at F out and replacing it with 17.
E is permanent 5th at 13, and G takes 13 + 5 = 18.
F is permanent 6th at 17. From F, G would be 17 + 3 = 20, no improvement on 18.
G is permanent 7th at 18. A1 for the final label at G.
Now work back from G, testing each edge at the junction you stand on against the difference of the labels at its ends. 18 − 13 = 5, the weight of EG, so EG is on the route; 13 − 11 = 2 while DE weighs 4, so DE is not on it, but 13 − 4 = 9 = BE, so BE is; and 4 − 0 = 4 = AB. M1 for testing label differences against the edge weights.
The shortest route is A, B, E, G, of length 18 km. A1 for the route.
Note that the route passes through E and not through D, even though D was made permanent first: a junction becoming permanent earlier says nothing about whether it lies on the route.

Question 13

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.

Accepted 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. 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.

Question 14

A network has vertices P, Q, R, S, T and edges PQ 4, PR 9, QR 3, QS 11, RS 5, RT 14 and ST 6. Use Dijkstra's algorithm to find the shortest route from P to T. Then find the least weight the edge RT could carry without that route ceasing to be shortest.

Accepted Answer

P is permanent 1st at 0, giving Q the working value 4 and R the working value 9. M1 for the first working values.
Q is permanent 2nd at 4. From Q, R improves from 9 to 7 and S takes 4 + 11 = 15. A1 for Q and R at 4 and 7.
R is permanent 3rd at 7. From R, S improves from 15 to 12 and T takes 7 + 14 = 21. A1 for S at 12.
S is permanent 4th at 12, and T improves from 21 to 18, becoming permanent 5th. Working back, 18 − 12 = 6 = ST, 12 − 7 = 5 = RS, 7 − 4 = 3 = QR and 4 = PQ, so the route is P, Q, R, S, T of length 18. A1.
Now let RT have weight w. R is permanent at 7 whatever w is, since RT is not used to reach R, so the route P, Q, R, T has length 7 + w. The printed route stays shortest while 7 + w ≥ 18, that is w ≥ 11. M1 for comparing 7 + w with 18, A1 for a least weight of 11.
At exactly 11 the two routes tie at 18 and both are shortest; below 11 the route P, Q, R, T wins outright.

Question 15

A network has 60 vertices. State how many entries Floyd's distance matrix holds and how many comparisons the algorithm makes in all. A single Dijkstra run on this network takes 0.05 seconds. Estimate the time taken to find the shortest distance between every pair of vertices by running Dijkstra from each vertex in turn, and compare the two methods.

Accepted Answer

The distance matrix is 60 by 60, so it holds 60 × 60 = 3600 entries. B1.
Floyd makes one iteration for each vertex, and each iteration compares every entry of the matrix once, so the total is 60 × 3600 = 60³ = 216 000 comparisons. M1 for cubing the number of vertices, A1 for 216 000.
Running Dijkstra from every vertex means 60 runs at 0.05 seconds each, about 3 seconds. M1 for 60 × 0.05, A1 for 3 seconds.
Each Dijkstra run is quadratic, so 60 of them is 60 × 60² = 60³ work as well: the two methods are of the same cubic order, and the choice between them turns on what is wanted rather than on speed. B1 for the comparison, with both methods placed at the same order. Floyd produces the route matrix alongside the distances in a single pass; repeated Dijkstra needs the backtrack to be done separately for each starting vertex, and is the better choice when only a few of the pairs are wanted.

Question 16

A network on P, Q, R, S has edges PQ 3, PR 10, QS 4 and RS 2, and no others. Write down the initial distance matrix, then carry out all four iterations of Floyd's algorithm, saying what each one changes and giving the final distance matrix.

Accepted 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. 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.