hungarian.go

package main

import (
	"fmt"
	"math"
)

func hungarianAlgorithm(costMatrix [][]int) ([]int, int) {
	rows := len(costMatrix)
	cols := len(costMatrix[0])

	// Step 1: Subtract the minimum value in each row from all elements in that row.
	for i := 0; i < rows; i++ {
		minVal := math.MaxInt32
		for j := 0; j < cols; j++ {
			if costMatrix[i][j] < minVal {
				minVal = costMatrix[i][j]
			}
		}
		for j := 0; j < cols; j++ {
			costMatrix[i][j] -= minVal
		}
	}

	// Step 2: Subtract the minimum value in each column from all elements in that column.
	for j := 0; j < cols; j++ {
		minVal := math.MaxInt32
		for i := 0; i < rows; i++ {
			if costMatrix[i][j] < minVal {
				minVal = costMatrix[i][j]
			}
		}
		for i := 0; i < rows; i++ {
			costMatrix[i][j] -= minVal
		}
	}

	// Step 3: Cover all the zeros with the minimum number of lines.
	rowCovered := make([]bool, rows)
	colCovered := make([]bool, cols)
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if costMatrix[i][j] == 0 && !rowCovered[i] && !colCovered[j] {
				rowCovered[i] = true
				colCovered[j] = true
			}
		}
	}

	// Step 4: Check if all rows are covered. If yes, the optimal assignment is found.
	assignment := make([]int, rows)
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if costMatrix[i][j] == 0 && !colCovered[j] && assignment[i] == 0 {
				assignment[i] = j
				colCovered[j] = true
				break
			}
		}
	}

	// Calculate the total cost of the assignment.
	totalCost := 0
	for i := 0; i < rows; i++ {
		j := assignment[i]
		totalCost += costMatrix[i][j]
	}

	return assignment, totalCost
}

func main() {
	// Define the cost matrix.
	costMatrix := [][]int{
		{3, 2, 7},
		{1, 4, 6},
		{5, 8, 9},
	}

	// Find the optimal assignment using the Hungarian Algorithm.
	assignment, totalCost := hungarianAlgorithm(costMatrix)

	// Print the result.
	fmt.Println("Assignment:")
	for i, j := range assignment {
		fmt.Printf("Worker %d assigned to Task %d\n", i, j)
	}
	fmt.Println("Total Cost:", totalCost)
}