Decision 3: Algorithms on Graphs

Question 1

What is a minimum spanning tree?

Answer 1

A spanning tree with minimum weight

Question 2

What is Kruskal’s algorithm? (3)

Answer 2

Order the arcs from smallest to largest
Add the lowest weight arc to the tree and then in weight order
Reject arcs that would form a cycle

Question 3

What is Prim’s algorithm? (3)

Answer 3

Starting from a given node, add the closest node
Then add the next closest node to either of the connected nodes
Repeat, each time adding the closest node until all have been added

Question 4

What is Prim’s from a matrix? (2)

Answer 4

Find the closest node to the start point, eliminating the rows of this node and the starting node
Continue adding the node that is the least distance from any of the connected nodes until each row has been crossed off

Question 5

What does Dijsktra’s algorithm do?

Answer 5

It finds the minimum distance between two points

Question 6

What is Dijkstra’s algorithm? (3)

Answer 6

Find the distance from the starting node to all connected nodes, making the second node the closest of these nodes
Continue from this node, finding the distance to any connected nodes and add the next smallest distance
Continue adding nodes until the graph is complete

Question 7

How is Dijsktra’s algorithm laid out? (3)

Answer 7

Each node has a box with three squares on top and one on the bottom
Top (left to right) - node letter, order added, minimum distance
Bottom - working out; add each distance, putting bigger distances in brackets

Question 8

What does Floyd’s algorithm do?

Answer 8

It finds the shortest path between any two vertices

Question 9

What is Floyd’s algorithm? (3)

Answer 9

Draw the preliminary tables, one shows the length of any direct route between nodes (otherwise use infinity) and the other shows the most direct route
In each iteration, test the nodes in order (A, B, C, D, etc.) and add corresponding rows and columns, replacing any larger number with a smaller number. Edit the route table and any replaced numbers should contain the letter of that iteration as a more direct route
In order to find the most direct route, use the route table to compare each pair of vertices between the two specified nodes until every intersection becomes a direct route