FM - Decision 1 - 3) Algorithms on graphs

Question 1

Definition of a minimum spanning tree

Answer 1

Spanning tree where the total length of its edges is as small as possible

Question 2

Method to find a minimum spanning tree using Kruskal’s algorithm

Answer 2

1. Sort all edges into ascending order of weight
2. Select any edge of least weight. If it would form a cycle, reject it. (If there are multiple valid edges of equal weight, choose whichever)
3. Repeat until all vertices are connected

Question 3

Method to find a minimum spanning tree using Prim’s algorithm

Answer 3

1. Choose any vertex to start the tree
2. Select the arc of least weight that joins a vertex already in the tree to one not yet in the tree. (If there are multiple valid edges of equal weight, choose whichever)
3. Repeat until all vertices are connected

Question 4

Method to find a minimum spanning tree using the distance matrix form of Prim’s algorithm

Answer 4

1. Choose any vertex to start the tree
2. Delete the row in the matrix of the chosen vertex
3. Number the column in the matrix of the chosen vertex
4. Circle lowest undeleted entry in the numbered columns. (If there are multiple valid entries, choose whichever)
5. The circled entry is the next edge to be added to the tree
6. Repeat until all rows have been deleted

Question 5

Method to find the shortest path between two vertices in a network using Dijkstra’s algorithm

Answer 5

1. Each vertex has an array of boxes → TL: vertex (letter) | TM: order of labelling (number order) | TR: final label (lowest working value) | B: working values
2. Label starting vertex with its letter, 1 order of labelling, and 0 final label
3. Record a working value (final label + weight of edge) at every non-completed vertex that it directly connects to
4. Whenever a working value is added, put brackets around the higher number
5. Choose the next vertex that has the lowest working value and label it fully. (If multiple vertices have the same smallest working value, choose whichever)
6. Repeat until destination vertex recieves its final label
7. To find the shortest path, trace back from destination to starting vertex → the correct edges are the ones where the weight of the arc = final label of later arc - final label of earlier arc. Then flip the order to go from starting to destination vertex