Library › Further Decision Mathematics 1 WDM11 › Shortest Path Algorithms

AS Level · Further Decision Mathematics 1 WDM11

Shortest Path Algorithms

Revise Shortest Path Algorithms for Further Decision Mathematics 1 WDM11 (AS Level) — revision notes and instant AI marking. Free to start.

📖 Revision notes · preview

Edexcel A Level Further Maths · Decision 1

Shortest Path Algorithms

Big idea: Dijkstra's algorithm finds the quickest way from one fixed starting point to everywhere else, while Floyd's algorithm finds the quickest way between every possible pair of points at once — same goal (shortest distance), different scale of ambition.

Summary — What This Chapter Covers

Dijkstra's algorithm finds the shortest distance from one fixed start vertex to every other vertex in a network (or you can stop early once you hit your target vertex).
Each vertex gets a labelling box with four values: the vertex name, its order of being finalised, its final (permanent) shortest distance, and its running "working values."
You build up the network by only ever looking at neighbours of the most recently finalised vertex, and you always keep the smallest working value seen so far.
Once every vertex (or your target) has a final label, you trace the shortest route backwards from the destination using the "difference in final labels = edge weight" trick.
Floyd's algorithm finds the shortest distance between every pair of nodes in a network — not just from one starting point — using two matrices: a distance matrix and a route matrix.
Floyd's algorithm updates both matrices in a fixed number of iterations (one per node), each time checking whether going "via" a particular node gives a shorter route.
Dijkstra = fast, but only from one start point. Floyd = slower, but gives you the whole picture for any start/end pair. Repeating Dijkstra from every possible start vertex would eventually give you the same information as one full run of Floyd's algorithm.

Key Vocabulary — Get Comfortable With These First

Vertex / Node

A point in the network (e.g. a town, a junction, a computer). The words "vertex" and "node" mean the same thing — Dijkstra's notes tend to say "vertex," Floyd's tend to say "node."

Edge / Arc

A connection between two vertices, usually with a number ("weight") attached representing distance, cost, or time.

Working value

A "temporary guess" at a vertex's shortest distance from the start. It can be beaten (replaced by something smaller) as the algorithm runs — it isn't locked in yet.

Final label (permanent label)

The confirmed, locked-in shortest distance from the start vertex to this vertex. Once a vertex has a final label, it never changes again.

Order of labelling

The sequence number showing which "round" a vertex got its final label in (1st, 2nd, 3rd...). The start vertex is always labelled 1st.

Distance matrix (Floyd's)

A grid showing the current best-known shortest distance between every pair of nodes. Starts off with only the direct edges filled in, and gets better with each iteration.

Route matrix (Floyd's)

A companion grid to the distance matrix. It doesn't store distances — it stores the "next stepping-stone node" to take on your way from the start to the destination.

Iteration

One full pass of Floyd's algorithm where a particular row and column are "highlighted" and used to try to improve every other cell. There's exactly one iteration per node in the network.

1. Dijkstra's Algorithm

What problem does it actually solve?

Imagine you're standing at a warehouse (your start vertex) and you want to know the shortest route to every single delivery address in your area. You don't want to solve "shortest route to address A," then separately solve "shortest route to address B" from scratch — that would be wasteful, because a lot of those routes overlap.

Dijkstra's algorithm is smart about this. It starts at your fixed vertex and grows outward like ripples on a pond, always finalising the closest unfinished vertex next. By the time it's done, you know the shortest distance from your start to every other vertex in the network — all in one pass.

If you only care about one destination, you can stop the moment that destination gets its final label — no need to finish labelling the rest of the network. This is exactly why Dijkstra's is fast in practice.

Fun fact from the notes A version of Dijkstra's algorithm was used in the classic Pacman video game to control how the ghosts chased Pacman around the maze!

The labelling box — read this carefully

Every vertex gets a small box with four pieces of information. Here's what each part means and where it sits:

LABELLING ORDER FINAL LABEL ↓ ↓ VERTEX → C │ 3 │ 5 └────── │ 8 │ 5 │ └────── ↑ WORKING VALUES

Box	What goes here
Vertex	The name of the vertex (e.g. "C")
Labelling order	Which numbered round this vertex became permanent in (1st, 2nd, 3rd...)
Final label	The confirmed shortest distance from the start vertex — this is the answer, once filled in
Working values	A running list of "current best guesses" — you can write several over time, but only the smallest (most recent, correctly-updated) one matters

Key relationship The final value in the "Working values" box will always end up being copied straight into the "Final label" box — they're the same number, just recorded in two places.

The six steps of Dijkstra's algorithm

1Draw a labelling box for every vertex in the network (if not already drawn), and write each vertex's name into its "Vertex" box.

2Complete the box for the start vertex: put 1 in the "Order of labelling" box, and 0 in the "Final label" box (distance from itself is always zero).

3Look at every vertex directly connected by an edge to the vertex whose final label was most recently completed — but only vertices that don't already have a final label. For each, write a working value = (final label of the vertex you're coming from) + (weight of the connecting edge). If a working value already exists there, only overwrite it if the new one is smaller.

4Scan across all vertices that currently have a working value but no final label yet. Find whichever has the smallest working value. Give that vertex the next order number, and copy its working value into its final label box — it's now permanent.

5Repeat steps 3 and 4 until your destination vertex gets its final label (or until every vertex has one, if you need the whole network).

6Trace the shortest path backwards from the destination to the start. Two vertices lie on the shortest path if the difference between their final labels equals the weight of the edge connecting them.

Examiner tip from the notes Don't cross out old working values when you replace them with something smaller — examiners want to see all your working clearly, including the values that got beaten.

Worked Example — Full Walkthrough

Network: A–B (9), A–C (12), A–F (5), A–G (8), B–C (4), C–G (9), C–D (4), F–G (2), F–E (4), G–E (1), E–D (7). Find the shortest path from A to D.

Step 2: Start vertex A → order = 1, final label = 0.

Round 1 (Step 3 from A): Neighbours of A are B, C, F, G. Working values: B = 9, C = 12, F = 5, G = 8.

Round 1 (Step 4): Smallest working value is F (5). → F gets order 2, final label 5.

Round 2 (Step 3 from F): F connects to G and E. Via F: G = 5 + 2 = 7 (smaller than the 8 we had — update it!). E = 5 + 4 = 9.

Round 2 (Step 4): Smallest unfinalised value now is G (7). → G gets order 3, final label 7.

Round 3 (Step 3 from G): G connects to C and E. Via G: C would be 7 + 9 = 16 (bigger than 12, so ignore). E would be 7 + 1 = 8 (smaller than 9 — update it!).

Round 3 (Step 4): Smallest unfinalised value now is E (8). → E gets order 4, final label 8.

Round 4 (Step 3 from E): E connects to D. Via E: D = 8 + 7 = 15.

Round 4 (Step 4): Compare B(9), C(12), D(15) — smallest is B (9). → B gets order 5, final label 9.

Round 5 (Step 3 from B): B connects to C. Via B: C would be 9 + 4 = 13 (bigger than 12 — ignore).

Round 5 (Step 4): Compare C(12), D(15) — smallest is C (12). → C gets order 6, final label 12.

Round 6 (Step 3 from C): C connects to D. Via C: D would be 12 + 4 = 16 (bigger than 15 — ignore).

Round 6 (Step 4): Only D left with a working value (15). → D gets order 7, final label 15.

Step 6 — trace backwards from D (final label 15):

Check	Calculation	Result
D → E	15 − 8 = 7	matches edge E–D (7) ✓
E → G	8 − 7 = 1	matches edge G–E (1) ✓
G → F	7 − 5 = 2	matches edge F–G (2) ✓
F → A	5 − 0 = 5	matches edge A–F (5) ✓

Result Shortest route: A → F → G → E → D, with total length 15.

Practice Questions — Dijkstra's

Question 1

In Dijkstra's algorithm, why do we only look at neighbours of the most recently finalised vertex in Step 3, rather than checking every vertex that's ever been finalised?

Question 2

A vertex X already has a working value of 14 written in its box. During a later round, you calculate a new possible working value of 17 coming from a different vertex. What should you do, and why?

2. Floyd's Algorithm

What problem does it actually solve?

Now imagine a completely different situation: you're building a delivery app where any customer might want to travel between any two points in the city — not always starting from the same warehouse. Running Dijkstra's algorithm over and over again (once per possible starting point) would eventually get you the answer, but that's a lot of repeated effort.

Floyd's algorithm solves this more directly. Instead of growing outward from one vertex, it works by asking a clever question over and over: "Is it shorter to go from node i to node j directly, or to go via some other node k?" It checks this question for every possible "via" node, one at a time, updating a table of best-known distances as it goes.

By the time it's finished, you have the shortest distance between every single pair of nodes in the network — not just from one fixed start.

Setting up the two matrices

Floyd's algorithm tracks two grids side by side, and updates both together at each step:

Distance matrix — the current best-known shortest distance between each pair of nodes.
Route matrix — for each pair of nodes, which node to go to next on the shortest path (not the whole path — just the next stepping stone).

Initial distance matrix

Fill in the direct distances between nodes straight from the network diagram. If there's no direct edge between two nodes, write ∞ (infinity) — this just means "we don't know a route yet, assume it's huge for now." Because most networks in this topic are undirected, the matrix will always come out symmetric (the distance from A to C is the same as from C to A) — this is a great way to double-check your work.

Initial route matrix

At the very start, before any clever routing has been considered, we simply assume the shortest way from any node to any other node is to go directly. So every cell just contains the name of the destination node itself (row = start, column = destination, cell = "go straight there").

Worked example set-up Network: A–B(7), A–C(5), A–D(10), B–C(4), B–E(3), C–D(6), D–E(3). No direct A–E link.

	A	B	C	D	E
A	–	7	5	10	∞
B	7	–	4	∞	3
C	5	4	–	6	∞
D	10	∞	6	–	3
E	∞	3	∞	3	–

Initial route matrix (every cell just says "go direct to the column node"):

	A	B	C	D	E
A	A	B	C	D	E
B	A	B	C	D	E
C	A	B	C	D	E
D	A	B	C	D	E
E	A	B	C	D	E

How each iteration actually works

Floyd's algorithm runs one iteration per node in the network. On the k-th iteration, you highlight the k-th row and k-th column of the distance matrix (they represent "distances involving node k").

Updating the distance matrix: for every other cell (except the "–" diagonal), add together the two highlighted values that line up with that cell (its row's highlighted value + its column's highlighted value). If that sum is smaller than the number currently sitting in the cell, replace it — you've just found a shortcut that goes "via" node k. If it's not smaller, leave the cell exactly as it is.

Example (iteration highlighting row A / column A): A B C D E A – 7 5 10 ∞ B (7) – 4 (17) 3 ← 7 + 10 = 17, and 17 < ∞, so UPDATE to 17 C 5 4 – 6 ∞ D 10 17 6 – 3 E ∞ 3 ∞ 3 – Row B, column D: 7 + 10 = 17, and 17 < ∞, so UPDATE to 17 (row D, column B updates the same way, by symmetry)

Golden rule For each cell (row i, column j): new candidate = (highlighted value in row i) + (highlighted value in column j). If candidate < current value in the cell → replace it. Otherwise → leave it alone.

Updating the route matrix at the same time: highlight the k-th column of the route matrix. Wherever a cell in the distance matrix got updated on this iteration, replace the matching cell in the route matrix with the node name k (the "via" node). This records: "to get from this row's node to this column's node, the next stepping stone is node k."

Why does this work? The route matrix doesn't try to store the whole path in one cell — that would be way too much information. Instead it just says "go here next." To build the full path, you keep looking up "what's next" over and over, hopping from stepping stone to stepping stone until you land on your destination.

Examiner tip from the notes You are very unlikely to be asked to complete all iterations of Floyd's algorithm from scratch in an exam — it's more common to be given matrices partway through (e.g. "after the 3rd iteration") and asked to continue from there. Make sure you can recognise which row/column would be highlighted next just from looking at how far through the matrices already are.

Reading off answers from the final matrices

Once every iteration is done, you're left with a final distance matrix and a final route matrix. Here's how to use them:

DShortest distance between any two nodes: just read the value straight out of the final distance matrix at that row/column intersection.

RShortest route between two nodes: start on the row for your starting node. Look under the column for your destination node — that cell tells you the next stepping-stone node. Move to the row for that stepping-stone node, and repeat, always checking the same destination column, until the cell you land on finally is the destination node itself.

Worked example — reading the final matrices:

Final distance matrix
	A	B	C	D	E
A	–	7	5	10	10
B	7	–	4	6	3
C	5	4	–	6	7
D	10	6	6	–	3
E	10	3	7	3	–

Row A, column E gives 10 — that's the shortest distance from A to E. Row B, column C gives 4 — the shortest distance from B to C (they're direct neighbours, so it makes sense this is just the edge weight).

Final route matrix
	A	B	C	D	E
A	A	B	C	D	B
B	A	B	C	E	E
C	A	B	C	D	B
D	A	E	C	D	E
E	B	B	B	D	E

Finding the route from B to D:

Start on row B. Look under column D (our destination) → the cell says E. So the first stepping stone is E.
Move to row E. Look under column D again → the cell says D. We've reached the destination!

Result Shortest route from B to D: B → E → D, with total length 6 (read from the distance matrix).

Practice Questions — Floyd's

Question 1

Why does the initial distance matrix always come out symmetric for an undirected network, and how can this fact help you check your work as you go?

Question 2

During the 4th iteration of Floyd's algorithm, you check a cell and find that (highlighted row value) + (highlighted column value) = 14, but the current value already sitting in that cell is 9. What do you do, and what does this tell you about the route?

3. Comparing Dijkstra's & Floyd's Algorithms

	Dijkstra's Algorithm	Floyd's Algorithm
Finds shortest path from...	One fixed start vertex to every other vertex	Any pair of start and end nodes
Best used when...	The starting point can't move (e.g. a power station, a distribution warehouse)	The starting point could be anywhere (e.g. a robot inspecting a pipeline network from various points)
Main advantage	Speed — can stop early once the target vertex is finalised	Amount of information — gives you everything, for every pair, in one go
Main disadvantage	Limited — only useful for routes starting from that one fixed vertex	Time — much slower to do by hand, since you must complete every iteration

The connection between them If you ran Dijkstra's algorithm once for every single vertex as the starting point (repeating it n times for n vertices), you'd eventually build up exactly the same information that one full run of Floyd's algorithm gives you. They're not really "different answers" — Floyd's is just a more efficient way of getting the "all pairs" version of what Dijkstra's gives you "one start point" at a time.

What to Memorise

Dijkstra's — the 6 steps in one line each

Draw labelling boxes for every vertex.
Start vertex: order = 1, final label = 0.
Find working values for all unlabelled neighbours of the most recently finalised vertex (only replace if smaller).
Finalise whichever unlabelled vertex has the smallest working value.
Repeat steps 3–4 until the destination (or whole network) is labelled.
Trace back: final label difference = edge weight, to find the path.

Floyd's — the core update rule

Distance matrix On iteration k: highlight row k and column k. For every other cell, if (row k's highlighted value) + (column k's highlighted value) < current cell value, replace it.

Route matrix Wherever the distance matrix changed on iteration k, write "k" into the matching cell of the route matrix (the new stepping-stone node).

Reading a route from the final route matrix Start on the row for your start node. Check the column for your destination. Follow the stepping stone. Repeat on the new row (same destination column) until you land on the destination itself.

Quick comparison to remember

Dijkstra: one start, fast, stoppable early. Floyd: all pairs, slower, needs full completion (one iteration per node).

Concepts Checklist

I can explain what problem Dijkstra's algorithm solves, and why it's useful for a fixed starting point.
I know all four parts of a Dijkstra labelling box (vertex, order, final label, working values).
I can carry out all 6 steps of Dijkstra's algorithm on a network by hand.
I know the rule for only updating a working value when the new one is smaller.
I can trace back the shortest path using the "difference in final labels = edge weight" rule.
I understand why Floyd's algorithm gives shortest distances between ALL pairs of nodes, not just from one start.
I can set up the initial distance matrix and initial route matrix from a network diagram.
I understand why undirected networks give symmetric distance matrices, and can use this as a check.
I can perform one iteration of Floyd's algorithm, updating both the distance and route matrices correctly.
I know there is exactly one iteration per node in the network.
I can read a shortest distance directly from the final distance matrix.
I can trace a full route through the final route matrix, stepping stone by stepping stone.
I can explain the advantages and disadvantages of Dijkstra's vs Floyd's algorithms.
I understand how repeating Dijkstra's from every vertex relates to a full run of Floyd's algorithm.

Exam Tips & Common Mistakes

Don't cross out old working values. Examiners want to see all your working, including values that were later beaten by a smaller one. Just write the new value alongside or below — don't erase history.

Only check neighbours of the most recently finalised vertex in Dijkstra's Step 3 — a common mistake is to re-check neighbours of vertices that were finalised earlier, which wastes time and can lead to incorrect "improvements" being applied out of order.

Use the symmetry check in Floyd's algorithm. If your distance matrix stops being symmetric partway through, you've made an error — go back through your last iteration before continuing.

The route matrix stores "next step," not the whole path. A very common error is trying to write a full route into a single cell. Remember: you always chase the trail cell-by-cell, using the same destination column each time, until you land on the destination.

You're unlikely to be asked to do every single iteration of Floyd's algorithm from scratch. Exam questions often give you matrices partway through (e.g. after the 3rd iteration) — practise recognising which row/column comes next so you're not thrown off.

Double-check your backward trace in Dijkstra's. The rule "difference in final labels = edge weight" only works between vertices that are actually directly connected by an edge — don't apply it to any random pair of vertices.

Remember what ∞ means in Floyd's initial matrix — it's not "no answer," it's a placeholder for "no direct link yet found," and it should always get replaced by a real number once the algorithm finds a route via some other node (unless the network is genuinely disconnected).

Also in the full note

3. Comparing Dijkstra's & Floyd's Algorithms
Exam Tips & Common Mistakes

What's inside

📖 Revision notes ✦ AI flashcards ✓ Instant AI marking

Read the full Shortest Path Algorithms notes free

That's the preview — create a free account to read the rest, plus flashcards and practice questions with instant AI marking. No credit card.

Unlock the full notes free →

Shortest Path Algorithms

Shortest Path Algorithms

Summary — What This Chapter Covers

Key Vocabulary — Get Comfortable With These First

1. Dijkstra's Algorithm

What problem does it actually solve?

The labelling box — read this carefully

The six steps of Dijkstra's algorithm

Worked Example — Full Walkthrough

Practice Questions — Dijkstra's

2. Floyd's Algorithm

What problem does it actually solve?

Setting up the two matrices

Initial distance matrix

Initial route matrix

How each iteration actually works

Reading off answers from the final matrices

Practice Questions — Floyd's

3. Comparing Dijkstra's & Floyd's Algorithms

What to Memorise

Dijkstra's — the 6 steps in one line each

Floyd's — the core update rule

Quick comparison to remember

Concepts Checklist

Exam Tips & Common Mistakes

More Further Decision Mathematics 1 topics