Network Algorithms

Question 1

How do you carry out Kruskal’s algorithm?

Minimum spanning network

Answer 1

• Select shortest edge
• Select next shortest edge that doesn’t create a cycle until all vertices are connected

Question 2

How do you carry out Prim’s algorithm?

Minimum spanning network

Answer 2

• Start with any vertex and delete its row
• Select smallest entry from that column and label the new vertice as 2 and delete its row
• Select smallest entry from any connected vertices’ columns and delete their rows until all finished

Question 3

How do you carry out Djikstra’s algorithm?

Shortest path from node to node

Answer 3

• Starting node labelled as (1 0)
• Write working values in all connected vertices (distance to starting node)
• Select node with smallest working distance and repeat process until final node has a permanent label

Question 4

CPA?

Answer 4

• Forward pass - longest time
• Backward pass - shortest time