Robinson Tuition
AS Decision Mathematics 1 · Edexcel 8FM0 · free Further Maths worksheet

Dijkstra's algorithm

Shortest path with labelling boxes (order of labelling, final value, working values), stating the route, routes that must pass through or avoid a vertex, changing a weight and re-solving.

12 original questions, 92 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

The network below shows the weights of the arcs joining six vertices, A to F.

Use Dijkstra's algorithm to find the shortest path from A to F. State the path and its length.

You should show, at each vertex, the order of labelling, the final value and the working values.

742698356ABCDEFDiagram NOT accurately drawn
5 marks
Show answer
ACBDF, length 17
2

The network below shows footpaths in a country park in the Peak District. The number on each arc is the time, in minutes, to walk along that path.

Priya walks from the car park, S, to the tea room, T.

  1. Use Dijkstra's algorithm to find the quickest route from S to T.
  2. State the time taken.

You should show, at each vertex, the order of labelling, the final value and the working values.

129754101116166891310SABCDEFTDiagram NOT accurately drawn
6 marks
Show answer
a) SADT b) 31 minutes
3

The network below shows streets in a town centre in Norfolk. The number on each arc is the driving time, in minutes. Arcs with an arrow are one-way streets and may only be used in the direction shown.

  1. Use Dijkstra's algorithm to find the quickest route from A to G and state its time.
  2. Explain why the quickest route from G back to A is not necessarily the route found in part (a) in reverse.

You should show, at each vertex, the order of labelling, the final value and the working values.

6435293611279ABCDEFGDiagram NOT accurately drawn
7 marks
Show answer
a) ABDEG; 21 minutes b) Some arcs are one-way, for example BE and DF, so they cannot be travelled from G towards A and the return route may use different arcs.
4

The network below shows the lengths, in km, of roads between eight towns, A to H, in Yorkshire.

  1. Use Dijkstra's algorithm to find the shortest route from A to H. State the route and its length.

Dijkstra's algorithm has order n2, where n is the number of vertices. A computer takes 0.6 seconds to apply the algorithm to a network with 40 vertices.

  1. Estimate the time the computer would take for a network with 250 vertices.

You should show, at each vertex, the order of labelling, the final value and the working values.

151183513121846911714ABCDEFGHDiagram NOT accurately drawn
8 marks
Show answer
a) ADGH; 33 km b) 23.4 seconds
5

The network below shows the lengths, in miles, of roads between eight villages, A to H, in Norfolk. Sam drives a mobile library van from A to H and must stop at village C on the way.

  1. Apply Dijkstra's algorithm, starting at C, to find the shortest distance from C to every other village.
  2. Hence find the shortest route from A to H that passes through C, and its length.
  3. The shortest route from A to H with no stop at C is 62 miles. Find how much further Sam drives because of the stop at C.

You should show, at each vertex, the order of labelling, the final value and the working values.

211730121625141128101982226ABCDEFGHDiagram NOT accurately drawn
8 marks
Show answer
a) D 16, A 17, F 27, B 28, E 30, G 40, H 48 b) ACDEGH; 65 miles c) 3 miles
6

The table shows the lengths, in km, of the direct cycle routes between seven towns, A to G, in Kent. A dash means there is no direct route.

ABCDEFG
A−241835−−−
B24−9−20−−
C189−1427−−
D35−14−−1640
E−2027−−825
F−−−168−19
G−−−402519−

Use Dijkstra's algorithm to find the shortest route from A to G and state its length. You may find it helpful to draw the network first.

You should show, at each vertex, the order of labelling, the final value and the working values.

6 marks
Show answer
ACDFG, 67 km
7

The network below shows the times, in minutes, for a bus to travel between stops S, A, B, C, D, E, F and T in a city in Wales.

  1. Use Dijkstra's algorithm to find the quickest route from S to T and state its time.

One week, stop B is closed for building work and the bus cannot pass through it.

  1. Use Dijkstra's algorithm again to find the quickest route from S to T that avoids B.
  2. State the increase in journey time.

You should show, at each vertex, the order of labelling, the final value and the working values.

8594612107118359107SABCDEFTDiagram NOT accurately drawn
9 marks
Show answer
a) SBET; 22 minutes b) SCFT; 24 minutes c) 2 minutes
8

The network below shows the times, in seconds, taken by a warehouse robot to travel between points A to H.

  1. Use Dijkstra's algorithm to find the quickest route from A to H and state its time.

A stack of pallets slows the robot down on DF, so the time for DF increases from 16 seconds to 34 seconds.

  1. Find the new quickest route from A to H and its time.
  2. State how much longer the new quickest route takes.

You should show, at each vertex, the order of labelling, the final value and the working values.

241982127221216293092318ABCDEFGHDiagram NOT accurately drawn
9 marks
Show answer
a) ABDFH; 84 seconds b) ACEGH; 88 seconds c) 4 seconds
9

The network below shows the distances, in hundreds of metres, between seven points, A to G, on a hospital site in Manchester.

  1. Use Dijkstra's algorithm to find the shortest distance from A to G.
  2. There is more than one shortest route from A to G. State every shortest route.

You should show, at each vertex, the order of labelling, the final value and the working values.

973811146616764ABCDEFGDiagram NOT accurately drawn
7 marks
Show answer
a) 29 b) ABDFG and ACFG
10

The network below shows the lengths, in km, of tracks in a forest in Hampshire. The length of track CF is x km.

  1. Given that x = 20, use Dijkstra's algorithm to find the shortest route from A to G and state its length.
  2. Find the range of values of x for which CF is on the shortest route from A to G.

You should show, at each vertex, the order of labelling, the final value and the working values.

10657912481056xABCDEFGDiagram NOT accurately drawn
8 marks
Show answer
a) ACDFG; 28 km b) 0 < x < 17
11

An ambulance is based at a hospital, H, in rural Northumberland. The network below shows the driving times, in minutes, between H and eight villages, A to G and J.

  1. Use Dijkstra's algorithm, starting at H, to find the shortest driving time from H to every village.
  2. State the quickest route from H to J and its time.
  3. The ambulance service aims to reach every village within 30 minutes. State, with a reason, whether this aim is met.
  4. Explain why one application of Dijkstra's algorithm is enough to answer parts (b) and (c).

You should show, at each vertex, the order of labelling, the final value and the working values.

149126411131157896123HABCDEFGJDiagram NOT accurately drawn
9 marks
Show answer
a) B 9, C 12, A 14, E 22, F 23, D 25, J 28, G 31 b) HBEJ; 28 minutes c) No: the quickest time to G is 31 minutes, more than 30 d) Once every vertex is labelled, each final value is the shortest distance from H to that vertex, so all the villages are answered at once.
12

The network below shows the lengths, in miles, of roads between ten places in Cumbria. A delivery driver starts at the depot, D.

  1. Use Dijkstra's algorithm to find the shortest route from D to K and state its length.

On Friday the driver must collect a parcel from E on the way from D to K.

  1. Use your answer to part (a) to find the shortest route from D to E.
  2. Hence find the shortest route from D to K that passes through E, and its length.
  3. Find how many extra miles the driver travels on Friday.

You should show, at each vertex, the order of labelling, the final value and the working values.

16111375181419691215138101117DABCEFGHJKDiagram NOT accurately drawn
10 marks
Show answer
a) DBFJK; 49 miles b) DBFE; 31 miles c) DBFEHK; 53 miles d) 4 miles

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All AS Decision Mathematics 1 topics