Consider a directed graph, G(N,A), where N and A are the set of nodes and arcs, respectively. Associated with each arc (i,j) in A is a cost c(i,j). Let |N|=n and |A|=m. The problem is to find a rooted directed spanning tree, G(N,S) where S is a subset of A such that the sum of c(i,j) for all (i,j) in S is minimized. The rooted directed spanning tree is defined as a graph which connects, without any cycle, all nodes with n-1 arcs, i.e., each node, except the root, has one and only one incoming arc.

The PRIM algorithm [1], which solves the undirected MST problem, is shorthanded to solve the directed counterpart. The following example exhibits that the iterative greedy decision may no longer sequentially give the optimal solution.

Chu and Liu [2], Edmonds [3], and Bock [4] have independently given efficient algorithms for finding the MST on a directed graph. The Chu-Liu and Edmonds algorithms are virtually identical; the Bock algorithm is similar but stated on matrices instead of on graphs. Furthermore, a distributed algorithm is given by Humblet [5]. In the sequel, we shall briefly illustrate the Chu-Liu/Edmonds algorithm, following by a comprehensive example (due to [1]). Reader can also refer to [6] [7] for an efficient implementation, O(mlogn) and O(n^2) for dense graph, of this algorithm.

1. Discard the arcs entering the root if any; For each node other than the root, select the entering arc with the smallest cost; Let the selected n-1 arcs be the set S.
2. If no cycle formed, G(N,S) is a MST. Otherwise, continue.
3. For each cycle formed, contract the nodes in the cycle into a pseudo-node (k), and modify the cost of each arc which enters a node (j) in the cycle from some node (i) outside the cycle according to the following equation.
   c(i,k)=c(i,j)-(c(x(j),j)-min_{j}(c(x(j),j))
   where c(x(j),j) is the cost of the arc in the cycle which enters j.
4. For each pseudo-node, select the entering arc which has the smallest modified cost; Replace the arc which enters the same real node in S by the new selected arc.
5. Go to step 2 with the contracted graph.

The key idea of the algorithm is to find the replacing arc(s) which has the minimum extra cost to eliminate cycle(s) if any. The given equation exhibits the associated extra cost. The following example illustrates that the contraction technique finds the minimum extra cost replacing arc (2,3) for arc (4,3) and hence the cycle is eliminated. (There is an error in the picture below. Arc (2,6) should be selected instead of Arc (1,6).)

1. E. Lawler, ``Combinatorial optimization: networks and matroids'', Saunders College Publishing, 1976.
2. Y. J. Chu and T. H. Liu, ``On the shortest arborescence of a directed graph'', Science Sinica, v.14, 1965, pp.1396-1400.
3. J. Edmonds, ``Optimum branchings'', J. Research of the National Bureau of Standards, 71B, 1967, pp.233-240.
4. F. Bock, ``An algorithm to construct a minimum spanning tree in a directed network'', Developments in Operations Research, Gordon and Breach, NY, 1971, pp. 29-44.
5. P. Humblet, ``A distributed algorithm for minimum weighted directed spanning trees'', IEEE Trans. on Communications, v.COM-31, n.6, 1983, pp.756-762.
6. R. E. Tarjan, ``Finding Optimum Branchings'', Networks, v.7, 1977, pp.25-35.
7. P.M. Camerini, L. Fratta, and F. Maffioli, ``A note on finding optimum branchings'', Networks, v.9, 1979, pp.309-312.