[wheels] Python wheels with maximum matching and minimum matching in weighted bipartite graph

The matching problem of weighted bipartite graph is often solved by Hungarian algorithm . The principle of the algorithm can be referred to 14-3: The maximum match in a weighted bipartite graph Maximum-Weight Bipartite Matching. Here is a library for solving matching problems ,pip Install the reference https://pypi.org/project/munkres/, Here is the source code provided ：

from munkres import Munkres, print_matrix
matrix = [[5, 9, 1],
[10, 3, 20],
[8, 7, 4]]# Bipartite graph adjacency matrix 
m = Munkres()
indexes = m.compute(matrix)
print_matrix(matrix, msg='Lowest cost through this matrix:')
total = 0
for row, column in indexes:
value = matrix[row][column]
total += value
print(f'({
row}, {
column}) -> {
value}')
print(f'total cost: {
total}')

The output is ：

Lowest cost through this matrix:
[ 5, 9, 1]
[10, 3, 20]
[ 8, 7, 4]
(0, 2) -> 1
(1, 1) -> 3
(2, 0) -> 8
total cost: 12

That is, the matching method of complete matching is (0, 2), (1, 1), (2, 0) Minimum loss can be obtained when , by 12. Pay attention to the input matrix Needs to be a list, Not for numpy, Otherwise, you will get the wrong result .

Reference material ：

1. https://stackoverflow.com/questions/4426131/maximum-weight-minimum-cost-bipartite-matching-code-in-python
2. https://stackoverflow.com/questions/4075669/hungarian-algorithm-in-python
3. https://software.clapper.org/munkres/