Decision Maths
Networks Prims Algorithm
Prim`s Algorithm
Wiltshire
In Lesson 1 we learnt about Kruskal`s algorithm,
which was used to solve minimum connector problems. Another method that can be used is Prim`s algorithm. Step 1 Select any node Step 2 Connect it to the nearest node Step 3 Connect one node already selected to the nearest unconnected node. Step 4 Repeat 3 until all nodes are connected.
Prim`s Algorithm
Select any node you like.
Lets select F.
Wiltshire
Consider the example we looked at last lesson.
Prim`s Algorithm
So connect E to D.
Wiltshire
The nearest to D, F or C is E which is 2 from D.
Prim`s Algorithm
Connect it to the nearest node.
Wiltshire
C and D are both 3 away so we can choose either.
Lets select C.
Prim`s Algorithm
only 3 away from F. So connect D to F.
Wiltshire
The nearest node to either of F or C is D, which is
Prim`s Algorithm
5 away from F. Connect A to F.
Wiltshire
The nearest to any of these four nodes is A which is
Prim`s Algorithm
We now need to connect the last node, B.
Wiltshire
The shortest arc is AB, which is 2.
Connect B to A.
Prim`s Algorithm
Wiltshire
All the nodes are now connected so this is the
minimum connector or minimal spanning tree.
Distance Table
Wiltshire
The Network can also be represented as a table.
The infinity symbol () means there is no edge
between the two nodes.
Prim`s on a Distance Table
Wiltshire
We are going to apply Prim`s algorithm to
the distance table. This demonstrates how a computer could apply the algorithm. Prim`s is more suitable than Kruskal`s as computers have a problem recognising loops. As you go through the algorithm, see if you can relate the procedure to the last example.
Prim`s on a Distance Table
Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7
Wiltshire
Select any arbitrary node. Delete the row and loop the column that correspond to the node selected. Choose the smallest number in the loop. Delete the row that this smallest number is in. Loop the column that corresponds to the row just deleted. Choose the smallest number in any loop. Repeat steps 4, 5 and 6 until all rows have been deleted and columns looped.
Prim`s on a Distance Table
Here I have chosen F.
Wiltshire
Select the smallest
Delete the row.
Loop the column.
number in the loop.
Prim`s on a Distance Table
Delete row C.
Wiltshire
Select the smallest
Loop column C.
number in any loop that is not crossed out.
Prim`s on a Distance Table
Delete row D.
Wiltshire
Select the smallest
Loop column D.
number in any loop that is not crossed out.
Prim`s on a Distance Table
Delete row E.
Wiltshire
Select the smallest
Loop column E.
number in any loop that is not crossed out.
Prim`s on a Distance Table
Delete row A.
Wiltshire
Select the smallest
Loop column A.
number in any loop that is not crossed out.
Prim`s on a Distance Table
Delete row B.
Wiltshire
Loop column B.
Prim`s on a Distance Table
Wiltshire
The algorithm is complete when all the columns have
been looped and the rows crossed out. The circles show the edges in the minimum connector.
Prim`s on a Distance Table
In this case they are AB, DE, AF, CF, DF
Wiltshire
Can you explain why this procedure is exactly the
same as applying Prim`s algorithm?
