In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).
The algorithm takes as input a directed graph D = ⟨ V , E ⟩ where V is the set of nodes and E is the set of directed edges, a distinguished vertex r ∈ V called the root, and a real-valued weight w ( e ) for each edge e ∈ E . It returns a spanning arborescence A rooted at r of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, w ( A ) = ∑ e ∈ A w ( e ) .
The algorithm has a recursive description. Let f ( D , r , w ) denote the function which returns a spanning arborescence rooted at r of minimum weight. We first remove any edge from E whose destination is r . We may also replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges.
Now, for each node v other than the root, find the edge incoming to v of lowest weight (with ties broken arbitrarily). Denote the source of this edge by π ( v ) . If the set of edges P = { ( π ( v ) , v ) ∣ v ∈ V ∖ { r } } does not contain any cycles, then f ( D , r , w ) = P .
Otherwise, P contains at least one cycle. Arbitrarily choose one of these cycles and call it C . We now define a new weighted directed graph D ′ = ⟨ V ′ , E ′ ⟩ in which the cycle C is "contracted" into one node as follows:
The nodes of V ′ are the nodes of V not in C plus a new node denoted v C .
If ( u , v ) is an edge in E with u ∉ C and v ∈ C (an edge coming into the cycle), then include in E ′ a new edge e = ( u , v C ) , and define w ′ ( e ) = w ( u , v ) − w ( π ( v ) , v ) .If ( u , v ) is an edge in E with u ∈ C and v ∉ C (an edge going away from the cycle), then include in E ′ a new edge e = ( v C , v ) , and define w ′ ( e ) = w ( u , v ) .If ( u , v ) is an edge in E with u ∉ C and v ∉ C (an edge unrelated to the cycle), then include in E ′ a new edge e = ( u , v ) , and define w ′ ( e ) = w ( u , v ) .For each edge in E ′ , we remember which edge in E it corresponds to.
Now find a minimum spanning arborescence A ′ of D ′ using a call to f ( D ′ , r , w ′ ) . Since A ′ is a spanning arborescence, each vertex has exactly one incoming edge. Let ( u , v C ) be the unique incoming edge to v C in A ′ . This edge corresponds to an edge ( u , v ) ∈ E with v ∈ C . Remove the edge ( π ( v ) , v ) from C , breaking the cycle. Mark each remaining edge in C . For each edge in A ′ , mark its corresponding edge in E . Now we define f ( D , r , w ) to be the set of marked edges, which form a minimum spanning arborescence.
Observe that f ( D , r , w ) is defined in terms of f ( D ′ , r , w ′ ) , with D ′ having strictly fewer vertices than D . Finding f ( D , r , w ) for a single-vertex graph is trivial (it is just D itself), so the recursive algorithm is guaranteed to terminate.
The running time of this algorithm is O ( E V ) . A faster implementation of the algorithm due to Robert Tarjan runs in time O ( E log V ) for sparse graphs and O ( V 2 ) for dense graphs. This is as fast as Prim's algorithm for an undirected minimum spanning tree. In 1986, Gabow, Galil, Spencer, and Tarjan produced a faster implementation, with running time O ( E + V log V ) .
