Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

LearnYMA01WDM11 · Decision Mathematics 1Algorithms on graphsDijkstra's and Floyd's algorithms

Algorithms on graphs · Subtopic 2 of 2

Shortest Paths

Dijkstra's algorithm finds the shortest route from one start vertex: give each vertex a working value, permanently label the smallest, update its neighbours, repeat. Trace back using edges where label difference equals edge weight. Floyd's algorithm finds shortest distances between every pair using a table, one vertex at a time.

Edexcel YMA01 WDM11Edexcel 9FM0 OptionAQA 7367 Paper 3≈ 45 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Apply Dijkstra's algorithm with working values and order of labelling.
Trace back the shortest route.
Apply Floyd's algorithm to distance and route matrices.

Pause and think

Your sat nav finds the fastest route among millions. Why doesn't it try every possible route?

Section 2 of 14

Core idea

Start hereSat nav thinking

Your sat nav doesn't try every road. It spreads out from where you are, settling the true shortest distance to one junction at a time, nearest first. That's Dijkstra's algorithm.

The big idea

Dijkstra: give the start label $0$ ; repeatedly make permanent the smallest working value, then update its neighbours with label $+$ edge. Trace the route back using edges where label difference equals weight.

1. Dijkstra

Network used below: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .

Worked exampleShortest $A$ to $E$

Find the shortest route from $A$ to $E$ .

Goal: Route and length.
Strategy: Label in order of smallest working value.

$A=0;\ C:3,\ B:4$
Neighbours of $A$ .
$C=3\ \text{(perm)};\ B:\min(4,5)=4,\ D:9,\ E:10$
Update from $C$ .
$B=4;\ D:\min(9,9)=9$
Update from $B$ .
$D=9;\ E:\min(10,12)=10;\ E=10$
Last labels.

Answer

ACE

, length

10

✓ CheckTrace back:

E-C=7=CE

✓;

C-A=3=AC

✓.

Why permanent labels are final

$v=\text{smallest working value}$
The vertex about to be made permanent.
$\text{any other route goes via an unlabelled }u$
Every alternative leaves the labelled set somewhere.
$\text{label}(u)\ge\text{label}(v)$
$v$ had the smallest working value.
$\text{weights}\ge0\Rightarrow\text{no shortcut}$
Adding non-negative weights can't make it shorter.

2. Floyd (all pairs)

Worked exampleOne Floyd update

$d_{BE}=\infty$ , $d_{BD}=5$ , $d_{DE}=3$ . Update using $D$ .

Goal: New $d_{BE}$ .
Strategy: $d_{BE}=\min(d_{BE},d_{BD}+d_{DE})$ .

$5+3=8<\infty$
Going via $D$ is better.
$d_{BE}=8,\ \text{route entry }D$
Update both tables.

Answer

d_{BE}=8

✓ Check

B\to D\to E

has length

8

✓.

Dijkstra loop

Drawing diagram…

Repeat until every vertex is permanent.

Common misconceptionNot nearest neighbour Compare all unlabelled working values, not just neighbours of the last vertex.

Edge caseNegative weights Dijkstra can fail if any weight is negative.

Pause and think

If $CE$ closes, what is the shortest $A$ to $E$ ?

Summary

Smallest working value → permanent.
Update with label $+$ edge.
Trace back by differences.
Floyd for all pairs.

Working value: Best distance found so far.
Permanent label: Confirmed shortest distance.

HistoryEdsger Dijkstra. Dijkstra designed his algorithm in 1956 in about twenty minutes at an Amsterdam café, to show off a new computer by finding routes between Dutch cities.

Fun factSix hops. Internet routers run a version of Dijkstra (OSPF) constantly to choose where to send your data packets.

Section 3 of 14

Key formulae

Update

\text{working value}=\min(\text{current},\ \text{label}+\text{edge})

Trace back

\text{label}(Y)-\text{label}(X)=w(XY)

Floyd

d_{ij}\leftarrow\min(d_{ij},\ d_{ik}+d_{kj})

TrickTrace from the end. Work backwards from the destination: an edge is on the route if the difference in final labels equals its weight.

Section 4 of 14

Worked examples

Example 1 · Dijkstra0 / 3 steps

Find the shortest route from

A

E

(

AB4

AC3

BC2

BD5

CD6

CE7

DE3

Section 5 of 14

Explore the graph

The example network

Loading the interactive graph…

Try this

Vertices: $A(0,2)$ , $B(2,4)$ , $C(2,0)$ , $D(4,4)$ , $E(5,1)$ . Weights: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .
Final labels from $A$ : $A0$ , $C3$ , $B4$ , $D9$ , $E10$ .

Shortest $A\to E$ : $ACE$ , $10$ .

In the real worldSat navs. Mapping apps use Dijkstra with extra tricks (like A*) to search millions of road links in milliseconds.

Section 6 of 14

Common mistakes

IncorrectLabelling the nearest neighbour of the last vertex

CorrectLabel the smallest working value anywhere

Dijkstra compares all unlabelled vertices.

IncorrectOverwriting working values with bigger ones

CorrectOnly replace if smaller

Keep the best so far.

IncorrectNegative weights

CorrectDijkstra needs non-negative weights

A permanent label could later be beaten.

Every route from A to E

Dijkstra: I'll check five, thanks.

Section 7 of 14

Exam tip

Exam tipBox layout. Use the exam's box: vertex, order of labelling, final value, then working values in order. Never erase working values.

Section 8 of 14

Guided practice

SA-DM-SP-G011 markL1 FoundationNon-calculatorDijkstra

In the network

AB4

AC3

BC2

BD5

CD6

CE7

DE3

, which value does

B

get as its final label from

A

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-SP-0012 marksL2 StandardNon-calculatorDijkstra

Find the shortest distance from

A

D

Salam Academy Original Practice · Proposed mark scheme

SA-DM-SP-0022 marksL2 StandardNon-calculatorDijkstra

Find the shortest distance from

A

E

Salam Academy Original Practice · Proposed mark scheme

SA-DM-SP-0031 markL2 StandardNon-calculatorFloyd

In Floyd's algorithm,

d_{BE}=\infty

d_{BD}=5

d_{DE}=3

. After the iteration using

D

, what is

d_{BE}

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-SP-0042 marksL3 ExamNon-calculatorDijkstra

If edge

CE

is closed for repairs, find the new shortest distance from

A

E

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Label the smallest working value.
Update neighbours.
Trace back by differences.
Floyd: all pairs.

Section 12 of 14

Quick quiz

Q1 · SA-DM-SP-Q011 markL1 FoundationNon-calculatorDijkstra

At each stage of Dijkstra's algorithm, the next vertex to receive a permanent label is

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: A level Further Mathematics 9FM0
Where: Decision 1 · Algorithms on graphs (Dijkstra) and Algorithms on graphs II (Floyd)
Expected: Dijkstra's algorithm with working values and order of labelling; tracing back the route; Floyd's algorithm with distance and route tables.
Calculator: Permitted; show enough working to earn the method marks.
Typical style: Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
Open in: YMA01 · WDM11 9FM0 · Option

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel YMA01, 2018 specification (official specification).