Y1 - Decision - C3 - Algorithms on Graphs

Question 1

3.1-3.2 What do Kruskal and Prim’s algorithms do?

Answer 1

They find the minimum spanning tree (MST) of a network

Question 2

3.1 Describe Kruskal’s algorithm

Answer 2

1. Sort the arcs in ascending order of weight
2. Select the arc of least weight to start the tree
3. Consider the next arc of least weight:
   i) If it would form a cycle, reject it
   ii) If it would not form a cycle, add it to the tree (if arcs are of equal weight consider each in turn)
4. Repeat (3) until all vertices are connected

Question 3

3.2 Describe Prim’s algorithm

Answer 3

1. Select any vertex to start the tree from (often given to you in the question)
2. Choose an arc of least weight connecting to the starting vertex that joins a vertex not currently in the tree (if there are a choice of equal arcs then choose randomly)
3. Repeat (2) until all vertices are connected

Question 4

3.3 Describe how you can apply Prim’s algorithm to a distance matrix

Answer 4

1. Choose any vertex to start the tree
2. Cross out the row containing that vertex
3. Number the column in the matrix for the chosen vertex
4. Ring the lowest remaining entry in the column (if equal, choose randomly)
5. The ringed entry becomes the next arc added to the tree
6. Repeat 2, 3, 4, & 5 until all rows are deleted

Question 5

3.3 What order is Prim’s algorithm?

Answer 5

n^3

Question 6

3.4 What is Dijkstra’s algorithm used for?

Answer 6

Dijkstra’s (‘Dike-stra’) algorithm is used to find the shortest path through a network

Question 7

3.4 Describe Dijkstra’s algorithm

Answer 7

1. Above every vertex there is a vertex label, order of labelling, final value, and working values
2. Label the starting vertex with a 1 and a final value of 0
3. Record a working value at every vertex that is connected to the vertex chosen
4. If this value is smaller than the current working value, cross the old value out
5. Look at the working values at all vertices without final labels, select the smallest working value and make it the final label
6. Repeat until the destination receives a final label

Question 8

3.4 How do you find the shortest path between 2 points on a network?

Answer 8

Work backwards, whichever arc equals the next vertex when you subtract the arc value is the correct path