Английская Википедия:Edmonds' algorithm
Шаблон:Short description Шаблон:About
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).
Algorithm
Description
The algorithm takes as input a directed graph <math>D = \langle V, E \rangle</math> where <math>V</math> is the set of nodes and <math>E</math> is the set of directed edges, a distinguished vertex <math>r \in V</math> called the root, and a real-valued weight <math>w(e)</math> for each edge <math>e \in E</math>. It returns a spanning arborescence <math>A</math> rooted at <math>r</math> of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, <math>w(A) = \sum_{e \in A}{w(e)}</math>.
The algorithm has a recursive description. Let <math>f(D, r, w)</math> denote the function which returns a spanning arborescence rooted at <math>r</math> of minimum weight. We first remove any edge from <math>E</math> whose destination is <math>r</math>. 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 <math>v</math> other than the root, find the edge incoming to <math>v</math> of lowest weight (with ties broken arbitrarily). Denote the source of this edge by <math>\pi(v)</math>. If the set of edges <math>P = \{(\pi(v),v) \mid v \in V \setminus \{ r \} \}</math> does not contain any cycles, then <math>f(D,r,w) = P</math>.
Otherwise, <math>P</math> contains at least one cycle. Arbitrarily choose one of these cycles and call it <math>C</math>. We now define a new weighted directed graph <math>D^\prime = \langle V^\prime, E^\prime \rangle</math> in which the cycle <math>C</math> is "contracted" into one node as follows:
The nodes of <math>V^\prime</math> are the nodes of <math>V</math> not in <math>C</math> plus a new node denoted <math>v_C</math>.
- If <math>(u,v)</math> is an edge in <math>E</math> with <math>u\notin C</math> and <math>v\in C</math> (an edge coming into the cycle), then include in <math>E^\prime</math> a new edge <math>e = (u, v_C)</math>, and define <math>w^\prime(e) = w(u,v) - w(\pi(v),v)</math>.
- If <math>(u,v)</math> is an edge in <math>E</math> with <math>u\in C</math> and <math>v\notin C</math> (an edge going away from the cycle), then include in <math>E^\prime</math> a new edge <math>e = (v_C, v)</math>, and define <math>w^\prime(e) = w(u,v) </math>.
- If <math>(u,v)</math> is an edge in <math>E</math> with <math>u\notin C</math> and <math>v\notin C</math> (an edge unrelated to the cycle), then include in <math>E^\prime</math> a new edge <math>e = (u, v)</math>, and define <math>w^\prime(e) = w(u,v) </math>.
For each edge in <math>E^\prime</math>, we remember which edge in <math>E</math> it corresponds to.
Now find a minimum spanning arborescence <math>A^\prime</math> of <math>D^\prime</math> using a call to <math>f(D^\prime, r,w^\prime)</math>. Since <math>A^\prime</math> is a spanning arborescence, each vertex has exactly one incoming edge. Let <math>(u, v_C)</math> be the unique incoming edge to <math>v_C</math> in <math>A^\prime</math>. This edge corresponds to an edge <math>(u,v) \in E</math> with <math>v \in C</math>. Remove the edge <math>(\pi(v),v)</math> from <math>C</math>, breaking the cycle. Mark each remaining edge in <math>C</math>. For each edge in <math>A^\prime</math>, mark its corresponding edge in <math>E</math>. Now we define <math>f(D, r, w)</math> to be the set of marked edges, which form a minimum spanning arborescence.
Observe that <math>f(D, r, w)</math> is defined in terms of <math>f(D^\prime, r, w^\prime)</math>, with <math>D^\prime</math> having strictly fewer vertices than <math>D</math>. Finding <math>f(D, r, w)</math> for a single-vertex graph is trivial (it is just <math>D</math> itself), so the recursive algorithm is guaranteed to terminate.
Running time
The running time of this algorithm is <math>O(EV)</math>. A faster implementation of the algorithm due to Robert Tarjan runs in time <math>O(E \log V)</math> for sparse graphs and <math>O(V^2)</math> 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 <math>O(E + V \log V)</math>.
References
External links
- Edmonds's algorithm ( edmonds-alg ) – An implementation of Edmonds's algorithm written in C++ and licensed under the MIT License. This source is using Tarjan's implementation for the dense graph.
- NetworkX, a python library distributed under BSD, has an implementation of Edmonds' Algorithm.
Шаблон:Graph traversal algorithms
