Edexcel IAL - Decision Mathematics 1- 2.2 Dijkstra’s Algorithm for Shortest Paths- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 2.2 Dijkstra’s Algorithm for Shortest Paths -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 2.2 Dijkstra’s Algorithm for Shortest Paths -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 2.2 Dijkstra’s Algorithm for Shortest Paths
Dijkstra’s Algorithm for Finding the Shortest Path
Dijkstra’s algorithm is a systematic method used to find the shortest path from a chosen starting vertex (the source) to all other vertices in a weighted network.
The algorithm works only for networks in which all edge weights are non-negative.
Purpose of Dijkstra’s Algorithm
- To determine the shortest distance from a starting vertex to a specified destination
- To find the shortest paths from the starting vertex to all other vertices
- Typical applications include route planning, transport networks, communication systems, and scheduling problems.
Key Features
- All edge weights must be positive or zero
- The algorithm builds up shortest paths step by step
- Once a vertex is labelled as final, its shortest distance is fixed
Outline of Dijkstra’s Algorithm
The algorithm uses temporary and permanent distance labels.
- Step 1: Label the starting vertex with distance 0 (permanent)
- Step 2: Label all other vertices with distance ∞ (temporary)
- Step 3: From the most recently permanent vertex, update temporary distances to adjacent vertices
- Step 4: Choose the vertex with the smallest temporary distance and make it permanent
- Step 5: Repeat Steps 3 and 4 until the destination vertex becomes permanent or all vertices are permanent
Distance Updating Rule
When updating distances, the rule used is:
$\text[New distance = (current permanent distance) + (edge weight)}$
If this value is smaller than the existing temporary distance, it replaces it.
Recording the Route
Alongside distances, the algorithm records the preceding vertex for each update.
This allows the actual shortest path to be traced back once the destination is reached
Important Examination Notes
- All edge weights must be non-negative
- Students must show clear step-by-step working
- Distances and routes should be clearly labelled
- The final shortest path and its total weight must be stated
Example
The weighted network has vertices \( \mathrm{A, B, C, D, E} \). Find the shortest path from A to E using Dijkstra’s algorithm.
Edges: AB(6), AC(2), BC(3), BD(5), CD(4), DE(2)
▶️ Answer / Explanation
| Vertex | Distance | Predecessor |
|---|---|---|
| A | 0 (P) | – |
| C | 2 (P) | A |
| B | 5 (P) | C |
| D | 6 (P) | C |
| E | 8 (P) | D |
Conclusion:
Shortest path: A → C → D → E
Shortest distance: \( \mathrm{8} \)
Example
A delivery vehicle starts at vertex P. Use Dijkstra’s algorithm to find the shortest distance from P to all other vertices.
Edges: PQ(4), PR(1), QR(2), QS(5), RS(8), RT(10), ST(2)
▶️ Answer / Explanation
| Vertex | Final distance | Shortest route |
|---|---|---|
| P | 0 | – |
| R | 1 | P |
| Q | 3 | P → R |
| S | 8 | P → Q |
| T | 10 | P → Q → S |
Conclusion:
The table gives the shortest distances and routes from P to every vertex.
Example
Using Dijkstra’s algorithm, vertex G becomes permanent with distance \( \mathrm{14} \).
Explain the meaning of this result.
▶️ Answer / Explanation
Once a vertex is labelled permanent, its distance cannot be reduced.
Conclusion:
The shortest possible distance from the starting vertex to G is \( \mathrm{14} \).
No alternative route exists with a smaller total weight.