2: Algorithms on Graphs

Question 1

Adjacency Matrix

Answer 1

Matrix, whose entries represent the number of edges joining the corresponding vertices

Question 2

Distance Matrix

Answer 2

Matix, whose entries represent the weight of each edge joining the corresponding vertices

Question 3

Minimum Spanning Tree

Answer 3

Spanning tree such that the total weight of its edges is as small as possible (a.k.a., MST / Minimum connector)

Question 4

Kruskal’s Algorithm (2, 1:3, 1)

Answer 4

1. Sort all the edges into ascending order of weight
2. Select the edge of least weight to start the tree
3. Consider the next edge of least weight:
   - If it would form a cycle with the edges already selected, reject it
   - If it does not form a cycle, add it to the tree
   - If there is a choice of equal edges, consider each in turn
4. Repeat step 3 until all vertices are connected

Question 5

Prim’s Algorithm (1, 1:2, 1)

Answer 5

1. Choose any vertex to start the tree
   2:
   - Select an arc of least weight that joins a vertex already in the tree to a vertex not already in the tree
   - If there is a choice of arcs of equal weight, choose any of them
2. Repeat step 2 until all the vertices are connected

Question 6

Distance Matrix Form of Prim’s Algorithm (6)

Answer 6

1. Choose any vertex to start the tree
2. Delete the row in the matrix for the chosen vertex
3. Number the column in the matrix for the chosen vertex
4. Put a ring around the lowest undeleted entry in the numbered columns
5. The ringed entry becomes the next arc to be added to the tree
6. Repeat steps 2 to 5 until all rows have been deleted

Question 7

Dijkstra’s Algorithm (1, 1:3, 3)

Answer 7

1. Label the start vertex, S, with the final label, 0
2. Record a working value at every vertex, Y, that is directly connected to the vertex, that has just received its final label, X:
   - Working value at Y = final label at X + weight of arc XY
   - If there is already a working value at Y, it is only replaced if the new value is smaller
   - Once a vertex has a final label, it is not revisited and its working values are no longer considered
3. Look at the working values at all vertices without final labels. Select the smallest working value. This now becomes the final label at that vertex. (If the two vertices have the same smallest working value, either may be given its final label first)
4. Repeat steps 2 and 3 until the destination vertex, T, receives its final label
5. To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB whenever: final label of B - final label of A = weight of arc AB. (If there’s more than one possible arc, choose either one)

Question 8

Floyd’s Algorithm (3, 1:2, 3)

Answer 8

1. Complete an initial distance table for the network. If there is no edge joining one vertex to another, label the distance infinity
2. Complete an initial route table by making every entry in each column the label at the top of that column
3. In the first iteration, copy the first row and first column values of the distance table and route table into two new tables. Lightly shade the values in the new distance table
4. Consider each unshaded position in turn. Compare the value in this position in the previous distance table with the sum of the corresponding shaded values:
   - If the sum ≥ the value, copy the value into the new distance table and copy the entry from the corresponding position in the previous route table into the new route table
   - If the sum < the value, copy the sum into the new distance table and write A in the corresponding position in the route table
5. For the second iteration, copy the second rows and the second columns from the last iteration into new distance and route tables. Lightly shade these values in the new distance table
6. Repeat step 4. This time any changes will result in a detour through B and so you should write B in the new route table, in each case, in the position corresponding to the changed value
7. If there are n vertices, completing the algorithm will require n iterations continuing in the same way