Network Algorithms

Question 1

Kruskal’s algorithm

Answer 1

• write all edges in order of size
• go through and select those which don’t create a cycle
• quadratic complexity

Question 2

Prims algorithm

Answer 2

• start at a point, and keep selected shortest routes out of nodes in range
• quadratic complexity

Question 3

Dijkstra’s algorithm

Answer 3

Quadratic complexity, with labels

Question 4

Prims incidence matrix

Answer 4

Start in one column, circle smallest, cross out row and label that row’s corresponding letter up north and repeat.