python实现匈牙利算法的代码

以下是Python实现匈牙利算法的代码：

def hungarian_algorithm(cost_matrix):
    num_rows = len(cost_matrix)
    num_cols = len(cost_matrix[0])

    # Step 1: Subtract the minimum value in each row from all values in that row
    for i in range(num_rows):
        min_val = min(cost_matrix[i])
        for j in range(num_cols):
            cost_matrix[i][j] -= min_val

    # Step 2: Subtract the minimum value in each column from all values in that column
    for j in range(num_cols):
        min_val = min(cost_matrix[i][j] for i in range(num_rows))
        for i in range(num_rows):
            cost_matrix[i][j] -= min_val

    # Step 3: Find a matching by finding augmenting paths
    match = [-1] * num_rows
    for i in range(num_rows):
        visited = [False] * num_cols
        if find_augmenting_path(cost_matrix, i, visited, match):
            match[i] = visited.index(True)

    # Step 4: Compute the total cost of the matching
    total_cost = sum(cost_matrix[i][match[i]] for i in range(num_rows) if match[i] != -1)

    return match, total_cost


def find_augmenting_path(cost_matrix, i, visited, match):
    num_cols = len(cost_matrix[0])

    for j in range(num_cols):
        if cost_matrix[i][j] == 0 and not visited[j]:
            visited[j] = True
            if match[j] == -1 or find_augmenting_path(cost_matrix, match[j], visited, match):
                match[j] = i
                return True

    return False

其中，`cost_matrix` 是一个二维列表，表示各个节点之间的成本。算法返回一个元组 `(match, total_cost)`，其中 `match` 是一个列表，表示匹配的结果，`match[i]` 表示左侧第 `i` 个节点匹配的右侧节点编号，若不存在匹配则为 `-1`；`total_cost` 表示匹配的总成本。