Imperial College London – Department of Computing
MSc in Computing Science
580: Algorithms
Tutorial: Graph Algorithms
1. Compute a minimum spanning tree for the graph below using Kruskal’s algorithm. List
the edges in the order they are added to the tree, and the weight of the tree after each
iteration. Whenever there is a choice of edges, pick the edge {u, v} that contains the
lowest vertex id.
Answer: The edges added are: (3, 4), (5, 7), (7, 8), (6, 7), (0, 9), (3, 7), (3, 9), (0, 2),
(0, 1).
2. Compute a minimum spanning tree for the same graph using Prim’s algorithm, starting
at vertex 5. List the vertices in the order they are added to the tree, and the weight of
the tree after each iteration. Whenever there is a choice of vertices, pick the one with the
lowest id.
Answer: The vertices (plus weight of tree) added are: 5(0), 7(-1), 8(-2), 6(-2), 3(-1),
4(-4), 9(-3), 0(-2), 2(0), 1(3).
1
3. Compute the shortest (lowest weight) path from A to each vertex of the graph below using
the Bellman–Ford algorithm. In each pass through the graph, use the order B, C, D, E,
A to determine the next vertex u for which all edges (u, v) should be relaxed. List the
estimated distance and the parent for each vertex after each pass.
Answer:
Iteration Distance(parent)
A B C D E
0 0(-) ∞(-) ∞(-) ∞(-) ∞(-)
1 0(-) 8(A) 5(A) 2(A) ∞(-)
2 0(-) 8(A) 3(D) 2(A) 9(B)
3 0(-) 6(C) 3(D) 2(A) 9(B)
4 0(-) 6(C) 3(D) 2(A) 7(B)
4. Compute the shortest (lowest weight) path from A to each vertex of the same graph using
Dijkstra’s algorithm. List the estimated distance and the parent for each vertex after each
iteration of the algorithm.
Answer:
Iteration Edges relaxed Distance(parent)
A B C D E
0 0(-) ∞(-) ∞(-) ∞(-) ∞(-)
1 (A,B) (A,C) (A,D) 0(-) 8(A) 5(A) 2(A) ∞(-)
2 (D,C) (D,E) 0(-) 8(A) 3(D) 2(A) 11(D)
3 (C,D) (C,B) (C,E) 0(-) 6(C) 3(D) 2(A) 9(C)
4 (B,E) 0(-) 6(C) 3(D) 2(A) 7(B)
2