Minimum spanning tree
A spanning tree such that the total length of its arcs is as small as possible. Can tell you smallest/cheapest/fastest way of linking all nodes
What does Kruskal’s algorithm do?
Find the minimum spanning tree
Kruskal’s algorithm
- Sort the arcs into ascending order of weight
- Select the arc of least weight to start the tree
- Consider the next arc of least weight
- if it would form a cycle with the arcs already selected, reject it
- if it does not form a cycle, add it to the tree - Repeat step 3 until all vertices are connected
Kruskal’s algorithm working
Write down edge, tick/cross if used, draw if necessary
Kruskal’s algorithm advantages and disadvantages
+ easy to follow
- weaker for many edges, difficult to check cycles
What does Prim’s algorithm do
Find the minimum spanning tree
Prim’s algorithm process
- Choose any vertex to start the tree
- Select an arc of least weight that joins a vertex in the tree to a vertex not in the tree and draw and note it down - can choose any if equal
- Repeat step 2 until all vertices are connected
What does Prim’s algorithm do if there are multiple
Gives you a different spanning tree depending on the starting node
What else can Prim’s algorithm be used on?
An undirected distance matrix
Prim’s algorithm on a distance matrix
- Choose any vertex to the start the tree
- Number the column 1 and cross that row
- Circle the smallest uncrossed value in a numbered column
- Take the node corresponding to that entry, label it’s column with the next number and delete the row
Repeat until all rows are crossed
What does Dijkstra’s algorithm do?
Find the shortest path from one node to all the others in a network
Dijkstra’s Algorithm Table
Vertex | Order of labelling | Final label
Working values
Dijkstra’s Algorithm Process
Label the start vertex with order 1 and final label 0
Assign a working value to all that can be reached from that vertex of final value of that + distance between, replacing the current value if it is lower
Give the vertex with lowest working label its final label and repeat until the destination vertex has its final label
How to find the shortest path from Dijkstra’s algorithm?
Trace back from the end vertex, taking paths where the final label of the vertex you are going to is equal to the final label of the current node minus the distance between
Floyd’s algorithm setup
- Complete an initial distance table for the network, with from on the left and to on top. If they aren’t connected by one arc, put an infinity symbol there
- Complete an initial route table by making every position the same as the label of its column
First iteration of Floyd’s algorithm
- Lightly shade row and column A of the initial distance table in and fill in another distance and route table with row and column A the same
- For each unshaded position in the new table, replace with the sum of the shaded values it shared a row/column with if it is lower than the present value
- If you replace them, put the letter of the row and column that are shaded into the route table and box each in square brackets
Further iterations of Floyd’s algorithm
Repeat, shading row and column B and so on
Unbox any values that were boxed on the last iteration
Finding a route from Floyd’s algorithm
Write down the start and end vertex with a gap in between
Using the final route table use the row of the start and column of the end to see if any nodes are used in between
Repeat this for any routes until all have been checked to be fastest direct
