Description

1. 1. d=∞, π=Nil
2. d=3, π=4
3. d=0, π=Nil
4. d=2, π=5
5. d=1, π=3
6. d=1, π=3

2.

3. Topological Order = p, n, o, s, m, r, y, v, x, w, z, u, q, t

4. Pass 1: (z,s), d=2, π=2, (z,x), d=2, π=2
Pass 2: (s,y), d=9, π=7, (x,t), d=5, π=-2
Pass 3: (y,x), d=6, π=-3
Pass 4: (x,t), d=4, π=-2

5.

6. Source = s
Iteration s t x y z
1 0 ∞ 5 ∞
2 0 9 5 ∞
3 0 9 5 11
4 0 9 5 11
5 0 9 5 11
d =

Iteration s t x y z
1 Nil s Nil Nil Nil
2 Nil s t s Nil
3 Nil s t s y
4 Nil s t s y
5 Nil s t s y
π=

Source = z
Iteration s t x y z
1 3 ∞ 7 ∞ 0
2 3 6 7 8 0
3 3 6 7 8 0
4 3 6 7 8 0
5 3 6 7 8 0
d =

Iteration s t x y z
1 z Nil z Nil Nil
2 z s z s Nil
3 z s z s Nil
4 z s z s Nil
5 z s z s Nil
π=

7. The minimum spanning tree of a graph is the union of minimum spanning trees of its connected components. The time complexity should be O(n) where n is the new set of edges to connect the incoming component. For the algorithm, first choose the remaining edge with the least weight and add it to the tree as long as it doesn’t create a cycle. Then find and delete the min-weight edge using something like a minheap. To detect cycles, if you add an edge, eliminate two trees and replace them with a tree containing the union of the nodes of the two eliminated trees. When n calls U and F, the time complexity is O(nlogn).