Algorithms on Graphs

Question 1

Minimum spanning tree

Answer 1

A spanning tree such that the total length of its arcs is as small as possible. Can tell you smallest/cheapest/fastest way of linking all nodes

Question 2

What does Kruskal’s algorithm do?

Answer 2

Find the minimum spanning tree

Question 3

Kruskal’s algorithm

Answer 3

1. Sort the arcs into ascending order of weight
2. Select the arc of least weight to start the tree
3. Consider the next arc of least weight
   - if it would form a cycle with the arcs already selected, reject it
   - if it does not form a cycle, add it to the tree
4. Repeat step 3 until all vertices are connected

Question 4

Kruskal’s algorithm working

Answer 4

Write down edge, tick/cross if used, draw if necessary

Question 5

Kruskal’s algorithm advantages and disadvantages

Answer 5

+ easy to follow

- weaker for many edges, difficult to check cycles

Question 6

What does Prim’s algorithm do

Answer 6

Find the minimum spanning tree

Question 7

Prim’s algorithm process

Answer 7

1. Choose any vertex to start the tree
2. Select an arc of least weight that joins a vertex in the tree to a vertex not in the tree and draw and note it down - can choose any if equal
3. Repeat step 2 until all vertices are connected

Question 8

What does Prim’s algorithm do if there are multiple

Answer 8

Gives you a different spanning tree depending on the starting node

Question 9

What else can Prim’s algorithm be used on?

Answer 9

An undirected distance matrix

Question 10

Prim’s algorithm on a distance matrix

Answer 10

1. Choose any vertex to the start the tree
2. Number the column 1 and cross that row
3. Circle the smallest uncrossed value in a numbered column
4. Take the node corresponding to that entry, label it’s column with the next number and delete the row
   Repeat until all rows are crossed

Question 11

What does Dijkstra’s algorithm do?

Answer 11

Find the shortest path from one node to all the others in a network

Question 12

Dijkstra’s Algorithm Table

Answer 12

Vertex | Order of labelling | Final label

Working values

Question 13

Dijkstra’s Algorithm Process

Answer 13

Label the start vertex with order 1 and final label 0
Assign a working value to all that can be reached from that vertex of final value of that + distance between, replacing the current value if it is lower
Give the vertex with lowest working label its final label and repeat until the destination vertex has its final label

Question 14

How to find the shortest path from Dijkstra’s algorithm?

Answer 14

Trace back from the end vertex, taking paths where the final label of the vertex you are going to is equal to the final label of the current node minus the distance between

Question 15

Floyd’s algorithm setup

Answer 15

1. Complete an initial distance table for the network, with from on the left and to on top. If they aren’t connected by one arc, put an infinity symbol there
2. Complete an initial route table by making every position the same as the label of its column

Question 16

First iteration of Floyd’s algorithm

Answer 16

1. Lightly shade row and column A of the initial distance table in and fill in another distance and route table with row and column A the same
2. For each unshaded position in the new table, replace with the sum of the shaded values it shared a row/column with if it is lower than the present value
3. If you replace them, put the letter of the row and column that are shaded into the route table and box each in square brackets

Question 17

Further iterations of Floyd’s algorithm

Answer 17

Repeat, shading row and column B and so on

Unbox any values that were boxed on the last iteration

Question 18

Finding a route from Floyd’s algorithm

Answer 18

Write down the start and end vertex with a gap in between
Using the final route table use the row of the start and column of the end to see if any nodes are used in between
Repeat this for any routes until all have been checked to be fastest direct