ConceptConceptDocsDocuments

Edexcel IAL Mathematics D1.2.2 Dijkstra’s shortest path algorithm

Practise Dijkstra’s algorithm by labelling network vertices, recovering the shortest route and interpreting via-point or path constraints.

Syllabus
First assessment 2019
Course
Mathematics YMA01
Level
AS

Exam points

  • Label vertices in Dijkstra order to obtain the shortest route between named vertices.
  • State both the route and total length, including journeys required to pass through a vertex.
  • Check whether a listed walk is a path by using repeated vertices and valid arcs.

D1.2.2 - Dijkstra’s algorithm for finding the shortest path question 1

[Maximum number: 6]
Figure 2

Figure 2

Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.

Figure for Question D1.2.2 - Dijkstra’s algorithm for finding the shortest path question 1 — Edexcel A-Level Mathematics AS

Shortest time to travel from A to J:
Quickest route from A to J:

Use Dijkstra's algorithm to find the shortest time needed to travel from A to J.

State the quickest route.
(6)

All question bank results loaded