Networks (Minimum Spanning Trees)

Question 1

What is a greedy algorithm?

Answer 1

A greedy algorithm is an algorithm that finds a solution to problems in the shortest time possible.

Question 2

Outline how Kruskal’s Algorithm works (Minimum Spanning Tree)

Answer 2

1) Select the shortest edge in a network
2) Select the next shortest edge
3) Repeat this process until all vertices are connected.
4) Make sure you do not create a cycle at any point, or it is not a tree.

Question 3

Outline how Prim’s Algorithm works (Minimum Spanning Tree)

Answer 3

1) From the starting vertex, select the shortest edge connected to that vertex.
2) Selected the shortest edge connected to all vertices already connected.
3) Repeat until all vertices are connected.

Question 4

Dijkstra’s Algorithm

Answer 4

• Start with first node, make number = 1, final value = 0
• Draw the running value in all connected nodes.
• Then take the node with the smallest running value, then we know that’s the final value.
• From that node see what you can go to (smallest weight), then others.
• Once you have exhausted a vertex, go to the next smallest working value.

Question 5

What are the defining characteristics of a critical activity?

Answer 5

• The early and late event time at the start and end of the activity are the same.
• E.g. 3 3 and 8 8