The Blossom Algorithm for Weighted Graphs
The Blossom Algorithm for Weighted Graphs
This Demonstration shows the steps of Edmonds's famous blossom algorithm for finding the perfect matching of minimal weight in a complete weighted graph. The algorithm uses and modifies a dual solution—the labels on the vertices—and tries to find a perfect matching using only equality edges (edges whose weight equals the sum of the labels at its ends). The matching is augmented by the augmenting tree method, but when that fails, the labels are changed. When blossoms (odd cycles) are found, they are shrunk.
The numbers in the grid are the weights (or the reduced weights) but with inactive edges (edges within a blossom) excluded; red entries denote equality edges and blue denotes the current matching. The colors on the graph vertices at the bottom-left represent the blossom groupings, and the blue text above the grid shows the values of the labels : the set of current labels of (derived) vertices. The edges in the two graphs at the bottom show the current matching (blue), the current tree edges (green), and the current active equality edges (red). The table at the upper-left shows the vertices in the current derived graph, with the pseudo-nodes colored to match the cycles they represent. The pseudo-nodes are also shown via the arrows at the far right, which indicate the current pseudo-node that contains a given vertex.
y