10.4.1 Dijkstra's Algorithm

Dijkstra's algorithm is a method for finding the shortest path from a starting node (source) to all other nodes in a weighted graph. This algorithm is widely used in network routing and optimisation problems.

How Dijkstra's Algorithm Works

Step-by-Step Process

Initialisation
Explore Neighbours
Mark as Visited
Move to the Next Node
Termination

Initialisation

Assign a tentative distance of $0$ to the starting node and $∞$ (infinity) to all other nodes.
Mark all nodes as unvisited and set the starting node as the current node.

Explore Neighbours

For the current node, calculate the tentative distance to each of its unvisited neighbours: $Tentative Distance to Neighbour$ = $Distance to Current Node+Weight of Edge to Neighbour\text{Tentative Distance to Neighbour} = \text{Distance to Current Node} + \text{Weight of Edge to Neighbour}$
If this calculated distance is less than the currently recorded tentative distance for that neighbour, update the neighbour's tentative distance.

Mark as Visited

Once all neighbours of the current node have been examined, mark the current node as visited. A visited node will not be checked again.

Move to the Next Node

Select the unvisited node with the smallest tentative distance as the new current node.
Repeat steps $2$ – $4$ until all nodes have been visited or the shortest path to the target node is determined.

Termination

The algorithm stops when the shortest path to the desired node is found (or when all nodes have been visited for a complete shortest-path map).

Worked Example

lightbulbExample

Example Find the shortest path from node $A$ to all other nodes in the weighted graph below:

Node Pair	Weight
A → B	4
A → C	2
B → C	5
B → D	10
C → D	3
C → E	4
D → E	1

Initialisation

Tentative distances:

\text{A: 0, B: ∞, C: ∞, D: ∞, E: ∞}

Current node: $A$

Step 1: Explore Neighbours of $A$

Distance to $B$ :

0 + 4 = 4

Distance to $C$ :

0 + 2 = 2

Update tentative distances:

\text{A: 0, B: 4, C: 2, D: ∞, E: ∞}

Mark $A$ as visited.

Step 2**: Move to** $C$ (Smallest Tentative Distance)

Distance to $B$ via $C$ : ( $B$ already has a shorter path: $4$ , so no change).

2 + 5 = 7

Distance to $D$ via $C$ :

2 + 3 = 5

Distance to $E$ via $C$ :

2 + 4 = 6

Update tentative distances:

\text{A: 0, B: 4, C: 2, D: 5, E: 6}

Mark $C$ as visited.

Step 3: Move to $B$ (Next Smallest Tentative Distance)

Distance to $D$ via $B$ : ( $D$ already has a shorter path: $5$ , so no change).

4 + 10 = 14

Update tentative distances (no changes):

\text{A: 0, B: 4, C: 2, D: 5, E: 6}

Mark $B$ as visited.

Step 4**: Move to** $D$

Distance to $E$ via $D$ : ( $E$ already has a path of $6$ , so no change).

5 + 1 = 6

Update tentative distances (no changes):

\text{A: 0, B: 4, C: 2, D: 5, E: 6}

Mark D as visited.

Step 5**: Move to** $E$

All nodes visited; algorithm terminates

Final Tentative Distances

\text{A: 0, B: 4, C: 2, D: 5, E: 6}

The shortest paths from $A$ are:

A → B: 4
A → C: 2
A → D: 5
A → E: 6

Note Summary

infoNote

Common Mistakes

Incorrect Initialisation Forgetting to set the starting node's distance to $0$ and all others to $∞$ .
Skipping Updates Failing to update the tentative distance of a node when a shorter path is found.
Revisiting Visited Nodes Including already visited nodes in further calculations.
Ignoring Edge Weights Treating all edges as having equal weight instead of using the given values.
Stopping Prematurely Not exploring all nodes, leading to incomplete or incorrect paths.

infoNote

Key Formulas/Theorems

Tentative Distance Update

\text{Tentative Distance to Neighbour} = \text{Distance to Current Node} + \text{Edge Weight}

Node Selection

\text{Next Node} = \text{Unvisited Node with Smallest Tentative Distance}

Algorithm Termination Stops when all nodes have been visited or the shortest path to the desired target node is finalised.

Dijkstra's Algorithm Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1