Decision chapter 3 - Algorithms on graphs

Question 1

What is a minimum spanning tree?

Answer 1

A spanning tree such that the total length of it’s arcs is as small as possible

Question 2

What is Kruskal’s algorithm used for?

Answer 2

To find the minimum spanning tree

Question 3

Describe how to carry out Kruskal’s algorithm

Answer 3

Sort the arcs into ascending orders of weight and use the arc of least weight to start the tree

Add arcs in ascending orders of weight unless an arc would form a cycle, in which case reject it

Question 4

What is Prim’s algorithm used for?

Answer 4

To find the minimum spanning tree

Question 5

Describe how to carry out Prim’s algorithm for a graph

Answer 5

Choose any vertex to start the tree

Select an arc of least weight that joins a vertex already in the tree to a vertex not yet in the tree

Repeat until all vertices are connected

Question 6

Describe how to carry out Prim’s algorithm for a distance matrix

Answer 6

Choose any vertex to start the tree

Delete the row in the matrix for the chosen vertex

Number the column in the matrix for the chosen vertex

Circle the lowest undeleted entry in the numbered columns which becomes the next arc

Repeat this until all rows are deleted

Question 7

What is Dijkstra’s algorithm used for?

Answer 7

Find the shortest path between 2 vertices in a network and each intermediate vertex completed on the way to the destination vertex. It’s also possible to use it on networks with directed arcs

Question 8

Describe how to carry out Dijkstra’s algorithm

Answer 8

Label the starting vertex with final value 0 (shortest distance from starting vertex)

Record a working value at every vertex that is directly connected to the vertex that has just received it’s final value label (Final label at previous vertex + Distance between arcs)

Select the smallest working value. This is the final label for that vertex

Repeat until the destination vertex receives it’s final label

Find the shortest path by tracing back from destination to start

(Include an arc AB on the route if B is already on the route and final label B - Final label A = Weight of arc AB)

Question 9

What is Floyd’s algorithm used for?

Answer 9

Find the shortest path between each pair of vertices in a network

Question 10

Describe how to carry out Floyd’s algorithm

Practice with questions, this revision card is bad

Answer 10

Complete an initial distance table for the network. If there is no direct route between vertices, label the distance with an infinity symbol

Complete an initial route table by making every entry in the first column the same as the label at the top of the first column, every entry in the second column the same as the label at the top of the second column and so on

In the first iteration, copy the first row and column values of the distance table into a new table. Lightly shade these

Consider each unshaded position in turn. Compare the value in this position in the previous table with the sum of the same column and row in the new table. if new value is ≥ old value, copy old value into new table. If new value < old value, copy new value into new table

In a new route table, copy the letter at the top of the column into any positions where there was a change in the distance table

Repeat the steps above for further iterations