D1: Chapter 3, Algorithms on Graphs
Joseph Kruskal Vojtěch Jarník Robert C. Prim Edsger W. Dijkstra
1928-2010 1897-1970 1921-2021 1930-2002
Ex 3A Kruskal’s
Ex 3B Prim’s
Ex 3C Prim’s from a matrix
Ex 3D Dijkstra’s
Ex 3E Floyd’s (A2)
Robert W. Floyd Stephen Warshall Bernard Roy Exam Questions
1936-2001 1935-2006 1934-2017
This whole chapter is concerned with applying algorithms to weighted graphs/networks in
order to find shortest distances between locations.
Kruskal’s and Prim’s Algorithms
Both of these algorithms aim to find a minimum spanning tree (MST) for a network.
This is a spanning tree such that the total weight is a small as possible.
The MST is sometimes referred to as a minimum connector.
If we were designing an algorithm to find the minimum spanning tree, we would want…
• To add the lowest weight edges first (otherwise it’s not minimum)
• To never create a cycle (otherwise it’s not a tree)
• To include every vertex (other it’s not spanning)
Kruskal’s Algorithm Prim’s Algorithm
Priorities (in order) Priorities (in order)
1) Add the smallest edges 1) Must be a tree (no cycles)
2) Must be a tree (no cycles) 2) Add the smallest edges
3) Include every vertex 3) Include every vertex
Kruskal’s often looks ‘Khaotic’ and doesn’t Prim’s always looks ‘neat’ or ‘Prim and proper’,
always resemble a tree until the end. as it will always grow as a tree does.
Kruskal's vs Prim's - visualisation
Both algorithms are greedy, always taking the lowest available edge – Kruskal’s can be anywhere,
but Prim’s must connect to somewhere already on the tree (and neither can create a cycle)
Kruskal’s Algorithm
Find the minimum spanning tree for the following network.
Priorities (in order) State the weight of the tree. (Use Kruskal’s)
1) Add the smallest edges
2) Must be a tree (no cycles)
3) Include every vertex
Tips:
• List the vertices in ascending order
• Indicate whether you accept or reject the
edge (examiners want to see this)
• If there is a choice of equal edges, pick
either – you will still find a MST, but could
end up with a different tree!
𝐴𝐵 31 𝐷𝐸 18 D1 June 2010
𝐴𝐶 30 𝐹𝐺 21
𝐵𝐷 24 𝐶𝐷 22
𝐵𝐻 38 𝐵𝐷 24
𝐶𝐷 22 𝐶𝐸 24
𝐶𝐸 24 𝐸𝐺 26
𝐶𝐹 29 𝐸𝐹 28
𝐷𝐸 18 𝐶𝐹 29
𝐷𝐻 34 𝐴𝐶 30
𝐸𝐹 28 𝐴𝐵 31
𝐸𝐺 26 𝐺𝐻 33
𝐹𝐺 21 𝐷𝐻 34
𝐺𝐻 33 𝐵𝐻 38
Prim’s Algorithm
Find the minimum spanning tree for the following network.
Priorities (in order) State the weight of the tree. (Use Prim’s starting at A)
1) Must be a tree (no cycles)
2) Add the smallest edges
3) Include every vertex
Tips:
• Write down the edges you accept in order
(examiners want to see this)
• Always check all the possible edges, not just
ones connected to the last vertex added
• Notice the edges don’t really need to be
ordered first – it is often quicker to use!
D1 June 2010
Your Turn
Find the minimum spanning tree for the following network.
State the weight of the tree. (Use Kruskal’s)
D1 June 2011
Find the minimum spanning tree for the following network.
State the weight of the tree. (Use Prim’s starting at A)
D1 June 2011
Ex 3A & 3B
Prim’s Algorithm – on a distance matrix
This is still pretty simple – add the smallest available edge to an
unconnected vertex. Prim’s Algorithm
Here are some tips to keep your thinking organised:
• Cross through a vertex’s row once it has been added, so you Priorities (in order)
don’t add it again! 1) Must be a tree (no cycles)
• Indicate at the top the order the vertices were added, examiners 2) Add the smallest edges
want to know this 3) Include every vertex
• Only pick values from these added columns, so the tree remains
connected
Apply Prim’s algorithm to the following distance matrix to find a minimum spanning tree.
Start at A. Indicate the order that you add the arcs.
Additional Example
Use Prim’s algorithm, starting at A, to solve the minimum connector problem for
this table of distances. Clearly state the order you selected the edges of your tree,
and the weight of your final tree. Draw your tree.
D1 Jan 2006
Your Turn
The table below shows the travel time, in seconds, for Tom to walk between different
departments in his sixth form college. Use Prim’s algorithm, starting at Drama, to find the
minimum spanning tree for the network. Indicate the order that the arcs were added.
D1 June 2014
Ex 3C
Order of Prim’s Algorithm
How many comparisons were made when applying Prim’s algorithm to
our previous example?
What about if it were an distance matrix?
State the order of the algorithm in terms of the number of vertices, .
Dijkstra’s Algorithm
Dijkstra’s algorithm aims to find the shortest path between a start vertex, and any other
vertex in the network.
Later, Floyd’s algorithm will improve on this, allowing us to find the shortest distance
between any two vertices in the network.
For example, what’s the shortest distance between and in the following network?
D1 June 2017
Here’s the logic behind Dijkstra’s Algorithm:
You want to find the shortest distance from a start vertex to all the vertices in the network - but it’s not always clear
which route provides that shortest distance, as there’s often many routes.
So, to tackle the problem, you want to find a vertex that you can guarantee has the shortest route. Start by finding the
closest vertex which is connected to the start vertex - you can guarantee this is the quickest route there, as all the
other routes would use edges which are longer.
Now you’ve guaranteed one shortest route, you can build on this by investigating other routes from this vertex. Add on
the distances of edges to other neighbouring vertices, keeping track of these distances. If you have found a shorter
route, you’ll want to use it!
Compare all the routes you’ve found, and only accept the shortest one available, as this is the only one you can
guarantee is the shortest! Keep going, and investigate in this way, and you’ll eventually have traced all the shortest
distances.
D1 June 2017 Let’s start the process, beginning at A:
• We can guarantee the shortest route to D Shortest
Route
distance
• From D, it’s quickest to get to C, and quicker
than going via other paths from A – this 𝐴𝐷
guarantees the route from A to C is shortest
via D 𝐴𝐶
• From A, C, and D, which is the quickest route 𝐴𝐵
to B? That’s our shortest route to B!
D1 June 2017
Use Dijkstra’s algorithm to find the shortest path from A to H.
State the shortest path and its length.
• Track the distances of vertices
connected to the start vertex (1).
• Label the closest vertex “(2)”.
• Track the distances of vertices
connected to (2).
Distances are always from (1).
• If a vertex has multiple distances
tracked, only consider the
smallest one.
• Consider all unlabelled vertices
and label the closest vertex “(3)”.
• Repeat the process of tracking
distances connected to (3), and
then labelling the next closest
unlabelled vertex “(4)”.
[Note that it might not be
connected to (3)!]
• Continue doing this until all
vertices are labelled.
Additional Example Use Dijkstra’s algorithm to find the shortest path from
a) A to J, stating the path and its length.
D1 IAL Jan 2018
b) D to H, via A, stating the path and its length.
You can also be asked to perform
the algorithm on a directed
graph. It’s the same process!
D1 Jan 2011
Your Turn
Use Dijkstra’s algorithm to find the shortest path from
a) A to H, stating the path and its length.
b) H to C, stating the path and its length.
Ex 3D
Exam Questions AS 2022
Part (a) is a quick sort
AS 2021
AS 2019
Floyd’s Algorithm (A2)
Floyd’s algorithm is an improvement on Dijkstra’s - it allows us to find the shortest distance
between any two vertices in the network. It can only be used on distance matrices, so if
you’re given a graph, convert it to a distance matrix first.
Initial Route Table
Here’s the logic behind Floyd’s Algorithm:
Initially, the route table just tells
us to go directly to the next
You have a distance table/matrix from a vertex, with no consideration of
network showing only the direct distances going via other vertices. This is
why the columns are identical
between vertices.
Systematically, you check to see if going After the algorithm is complete,
via different vertices will reduce the the route table now tells us
which vertices we should travel
distance between all pairs. If it does, take via to reduce the distance.
that new distance, and record that the
Final Route Table
path should go via that vertex to reduce
Using the final table, how
the distance. should I travel from B to C?
From C to D?
Complete this process by checking the
routes going via all the vertices. Once you
finish, you’ll have recorded all the shortest
paths, and which vertices they should go
via.
Examples 𝐴 4 𝐵
7
Use Floyd’s algorithm to produce a table of shortest distances. 𝐶
1
You should give the distance table and route table for each iteration. 9
Find the route of minimum length from C to D.
𝐷
When considering going via A, compare each
cell’s value to the sum of the corresponding 𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫
2nd iteration (via B)
values in A’s column and row. If the cell value 𝑨 − 𝑨
is bigger, replace it with the smaller sum, and 𝑩 − 𝑩
indicate that going via A will reduce the
𝑪 − 𝑪
route. Repeat for all vertices.
𝑫 − 𝑫
No direct route is indicated with ∞
𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫
3rd iteration (via C)
𝑨 − 4 7 ∞ 𝑨 𝐴 𝐵 𝐶 𝐷 𝑨 − 𝑨
Initial table
𝑩 4 − ∞ 9 𝑩 𝐴 𝐵 𝐶 𝐷 𝑩 − 𝑩
𝑪 7 ∞ − ∞ 𝑪 𝐴 𝐵 𝐶 𝐷 𝑪 − 𝑪
𝑫 1 9 ∞ − 𝑫 𝐴 𝐵 𝐶 𝐷 𝑫 − 𝑫
𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫 𝑨 𝑩 𝑪 𝑫
1st iteration (via A)
4th iteration (via D)
𝑨 − 𝑨 𝑨 − 𝑨
𝑩 − 𝑩 𝑩 − 𝑩
𝑪 − 𝑪 𝑪 − 𝑪
𝑫 − 𝑫 𝑫 − 𝑫
It’s to be expected to carry out the full algorithm, and often get asked to complete 1-3
iterations. You can also be given the final tables and be asked to interpret them.
Perform the first two iterations of Floyd’s algorithm.
𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐴 − 15 35 27 32 14 𝐴 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐵 15 − 20 11 ∞ ∞ 𝐵 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐶 35 20 − 7 15 ∞ 𝐶 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐷 27 ∞ 7 − ∞ 16 𝐷 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐸 ∞ ∞ 15 21 − 15 𝐸 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐹 14 ∞ ∞ 16 15 − 𝐹 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
1st iteration (via A) 2nd iteration (via B)
𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹
𝐴 − 𝐴 𝐴 − 𝐴
𝐵 − 𝐵 𝐵 − 𝐵
𝐶 − 𝐶 𝐶 − 𝐶
𝐷 − 𝐷 𝐷 − 𝐷
𝐸 − 𝐸 𝐸 − 𝐸
𝐹 − 𝐹 𝐹 − 𝐹
8 departure gates in an airport are linked by a system of travellators and escalators.
Each gate is represented by a letter, to . The final distance and route tables are
shown below after Floyd’s algorithm has been applied with 8 iterations. The distances
represent the travel time, in minutes, between gates.
Find the shortest route from gate to gate . State the minimum time needed to make
this journey and determine the route that should be taken.
Ex 3E
Exam Question (A2 content) A2 2020
Some parts of the question have been
removed as they use content from Ch4/Ch5
