(Minimum Weight Spanning Trees) Given a graph (N , A) and a weight wij for each arc (i, j), consider the problem of finding a spanning tree with minimum sum of arc weights. This is not a shortest path problem and in fact it is not even a special case of the minimum cost flow problem. However, it has a similar graph structure to the one of the shortest path problem. Note that the orientation of the arcs does not matter here. In particular, if (i, j) and (j, i) are arcs, any one of them can participate in a spanning tree solution, and the arc having greater weight can be a priori eliminated.
(a) Consider the problem of finding a shortest path from node 1 to all nodes with arc lengths equal to wij . Give an example where the shortest path spanning tree is not a minimum weight spanning tree.
(b) Let us define a fragment to be a subgraph of a minimum weight spanning tree; for example the subgraph consisting of any subset of nodes and no arcs is a fragment. Given a fragment F, let us denote by A(F) the set of arcs (i, j) such that either i or j belong to F, and if (i, j) is added to F no cycle is closed. Show that if F is a fragment, then by adding to F an arc of A(F) that has minimum weight over all arcs of A(F) we obtain a fragment.
(c) Consider a greedy algorithm that starts with some fragment, and at each iteration, adds to the current fragment F an arc of A(F) that has minimum weight over all arcs of A(F). Show that the algorithm terminates with a minimum weight spanning tree.
(d) Show that the complexity of the greedy algorithm is O(NA), where N is the number of nodes and A is the number of arcs.
(e) The Prim-Dijkstra algorithm is the special case of the greedy algorithm where the initial fragment consists of a single node.
Provide an O(N2), implementation of this algorithm. Hint: Together with the kth fragment Fk, maintain for each j /∈ Fk the node nk(i) ∈ Fk such that the arc connecting j and nk(i) has minimum weight