Decision Maths: 3. Algorithms On Graphs

Question 1

What is a minimum spanning tree

Answer 1

A minimum spanning tree is a tree of minimum total weight that connects all of the nodes.

Question 2

Method for Kruskal’s Algorithm

Answer 2

1. List the edges in order of weight, smallest first.
2. Choose the edge with the smallest weight.
3. From the remaining edges, choose the edge with the smallest weight, as long as it does not form a cycle with the edges already chosen.
4. Repeat step 3 until all the vertices have been included.

(5. Then add all the edge weights together to find a total weight).

Question 3

Method for Prim’s Algorithm

Answer 3

1. Choose a start vertex
2. Connect the start vertex to the nearest new vertex by adding the shortest edge.
3. From any vertex on the tree so far, add the shortest edge that connects a new vertex
4. Repeat step 3 until all the vertices have been included.

(5. Then add the weights of each of the edges to find the total weight.)

Question 4

Advantages and Disadvantages of Kruskal’s and Prim’s

Answer 4

• Kruskal’s algorithm is very intuitive but it takes quite a lot of a work to sort the edges before you start.
• In a large network checking for cycles can be tricky
• Prim’s algorithm is also quite intuitive and is easier to use on a large network

Question 5

Method for Prim’s Algorithm for a Matrix

Answer 5

1. Choose a start vertex. Label the column corresponding to that vertex with a 1 and cross out / delete that row.
2. Look in all columns that have been numbered so far. Circle the smallest undeleted entry and read off the vertex for the row.
3. Label the column corresponding to this vertex with the next available label then delete the row.
4. Repeat steps 2 and 3 until all rows have been deleted

(5. Draw out the corresponding graph while doing steps 2 and 3)

(6. Then add the weights of all the arcs to find the total weight of the graph)

Question 6

Method for doing Dijkstra’s Algorithm for labelling the vertices (find the min distance/time)

Answer 6

Step 1:
Give the start vertex (S) a permanent label of 0.

Step 2:
Give each vertex connected to S a working value by recording its distance from S.

Step 3:
Find the smallest working value and give the corresponding vertex V this value as a permanent label.

Step 4:
Update working values at any unlabelled vertices that can be reached from V.

Step 5:
Repeat steps 3 and 4 until the destination vertex has been given a permanent label.

Question 7

What happens if 2 working values are joint smallest (which one do you choose)

Answer 7

If 2 working values are joint smallest, it doesn’t matter which one you choose.

Question 8

Method for doing Dijkstra’s Algorithm for Backtracking (finding the route)

Answer 8

Step 1:
Start from the destination vertex.

Step 2:
From the current vertex V, look at at the vertices that lead directly to V.

Step 3:
Of these vertices, vertex P is the previous vertex on the route if ‘Label at V’ - ‘Label at P’ = ‘Weight (PV)’

Step 4:
Repeat steps 2 and 3 using the vertex just found as the current vertex

Step 5:
Stop when you have backtracked all the way through the graph to the start vertex .

(Remember to flip the order of the vertices so it goes from start to finish)

Question 9

What does Floyd’s Algorithm do

Answer 9

Floyd’s algorithm is used to find the shortest route between any pair of vertices on a graph

Question 10

What does Dijkstra’s Algorithm do

Answer 10

Dijkstra’s algorithm only finds the shortest route between a start node and the rest.