Edmonds-Chu-Liu Algorithm

overview

Summary

Edmonds-Chu-Liu finds a minimum-cost arborescence: a directed, rooted spanning tree that minimizes total edge weight. It works by selecting one minimum incoming edge per node, contracting any cycles, adjusting weights, and recursing. The algorithm is the directed analog of minimum spanning tree methods like Kruskal or Prim. It is widely used when edges are directed, such as dependency parsing, network design, and flow initialization.