Decision Maths: Shortest Paths and Route Inspection
In A-level Further Maths' Decision Maths module, Dijkstra's algorithm finds the shortest path (and its length) from a start vertex to every other vertex in a weighted network, by repeatedly making permanent the smallest 'working value' among the unlabelled vertices and updating its neighbours. The route inspection problem (the 'Chinese postman problem') finds the shortest route that traverses every edge of a network at least once and returns to the start; it depends on the vertices of odd degree, since a route can use every edge exactly once only if every vertex has even degree, so some edges on the shortest path(s) between the odd vertices must be repeated.
Before you start
Make sure you're comfortable with these topics first:
Method
- Dijkstra's algorithm: give the start vertex a permanent (final) value of 0; for each vertex just made permanent, calculate a working value for each unlabelled neighbour as (permanent value + edge weight), keeping the smaller value if more than one route reaches that vertex.
- At each step, make permanent the smallest working value among all vertices not yet permanent, and record its predecessor (the vertex it was reached from), to allow the route to be traced back once the algorithm finishes.
- Repeat until the destination (or every vertex) has a permanent label; trace the shortest path by working backwards through predecessors from the destination to the start.
- Route inspection: find the degree of every vertex (the number of edges meeting there); a vertex has odd degree if an odd number of edges meet there.
- If there are exactly two odd vertices, find the shortest path between them (using Dijkstra's algorithm if needed) and repeat (duplicate) every edge on that path.
- If there are four (or more) odd vertices, list every way of pairing them up, find the total shortest-path weight for each pairing, and choose the pairing with the smallest total; duplicate the edges on the shortest paths of that pairing.
- The length of the optimal route = total weight of every edge in the network + the minimum total weight of the repeated edges found from the pairing (0 if there are no odd vertices, since the network then already has a route using every edge exactly once).
Worked example
A network has vertices S, A, B, C, D, T, with edges (weights): S-A 4, S-B 2, A-B 1, A-C 5, B-C 8, B-D 6, C-D 3, C-T 4, D-T 2. Use Dijkstra's algorithm to find the shortest path from S to T and state its length.
- Label S with permanent value 0. Its neighbours are A and B: working value of A = 0+4 = 4, working value of B = 0+2 = 2.
- The smallest working value is B (2), so B becomes permanent with predecessor S. From B, update its neighbours: A = min(4, 2+1) = 3 (predecessor B), C = 2+8 = 10, D = 2+6 = 8.
- The smallest remaining working value is A (3), so A becomes permanent with predecessor B. From A, update C = min(10, 3+5) = 8 (predecessor A).
- The smallest remaining working value is C (8), so C becomes permanent with predecessor A. From C, T = 8+4 = 12; D stays at 8, since 8+3 = 11 is not smaller.
- The smallest remaining working value is D (8), so D becomes permanent with predecessor B. From D, update T = min(12, 8+2) = 10 (predecessor D).
- T becomes permanent with value 10 and predecessor D. Tracing predecessors back from T gives T <- D <- B <- S.
- Final answer: shortest path is S - B - D - T, with total length 10.
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1Define the 'degree' of a vertex in a network.Show answer
Answer: The number of edges meeting at that vertex (a loop at a vertex counts twice towards its degree).
Q2A network has edges (weights): P-Q 3, P-R 6, Q-R 2, Q-S 8, R-S 4. Use Dijkstra's algorithm to find the shortest path from P to S and its length.Show answer
Answer: Path P-Q-R-S, length 9 (P=0; Q becomes permanent at 3; R updates to min(6,3+2)=5 and becomes permanent; S updates to min(3+8,5+4)=9).
Q3A network has exactly two vertices of odd degree. Explain, in terms of the route inspection algorithm, which edges must be repeated to obtain the shortest route that traverses every edge and returns to the start.Show answer
Answer: The edges on the shortest path between the two odd vertices must be repeated (duplicated); this is the minimum extra distance needed to make every vertex even degree, so that a route exists which uses every edge and returns to the start while repeating as little distance as possible.
Q4A network has total edge weight 84 and exactly two odd vertices, X and Y, with shortest distance 11 between them. Find the length of the optimal route that traverses every edge and returns to the start.Show answer
Answer: 95 (84 + 11).
Q5A network has six vertices of odd degree. Explain why the route inspection algorithm cannot simply repeat the edges on the single shortest path between the two closest odd vertices, and must instead compare ways of pairing up all six.Show answer
Answer: Repeating only the shortest path between two of the six odd vertices would fix those two but leave the other four still odd, so the network still would not have a route using every edge and returning to the start; all six odd vertices must be split into three pairs, every possible way of pairing them found, the total shortest-path distance of each pairing compared, and the pairing with the smallest total chosen.
Q6A delivery network has total weight 120 and all 6 of its vertices have even degree. Find the length of the shortest route that traverses every edge and returns to the start, explaining your reasoning.Show answer
Answer: 120 (no edges need repeating); since every vertex has even degree, the network already has a route (an Eulerian circuit) that covers every edge exactly once and returns to the start.
Q7Explain why the route inspection algorithm requires finding the vertices of odd degree, rather than looking at all vertices.Show answer
Answer: A route that uses every edge exactly once and returns to its start exists only if every vertex has even degree, because a route entering and leaving a vertex uses its edges in pairs; a vertex of odd degree cannot have all its edges paired off, so odd vertices are the 'problem points' that require some edges to be repeated.
Exam-style questions
Written in the style of a A Level Further Maths exam paper, with a full mark scheme.
A network representing a delivery round has vertices A, B, C, D, E, F and edges (weights): A-B 5, A-C 7, B-C 4, B-D 6, C-D 3, C-E 8, D-E 2, D-F 9, E-F 5. A vehicle must traverse every edge at least once and return to its starting point. (a) Find the degree of each vertex and identify the odd vertices. (b) Find the shortest path between the odd vertices. (c) Hence find the length of the shortest possible route.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 8 available
A network has vertices M, N, O, P, Q and edges (weights): M-N 2, M-O 9, N-O 4, N-P 7, O-P 5, O-Q 6, P-Q 1. Use Dijkstra's algorithm to find the shortest path from M to Q and state its length.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 5 available
A network has exactly four odd vertices: J, K, L, M. The shortest distances between each pair are: J-K = 6, J-L = 9, J-M = 5, K-L = 4, K-M = 8, L-M = 3. The total weight of the network is 60. Find the minimum length of a route that traverses every edge and returns to the start.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 4 available
See real A Level Further Maths past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the decision maths: shortest paths and route inspection worksheet pack - 10 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on decision maths: shortest paths and route inspection, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.