18

2

5

4

# Munkres

Julia implementation of the Hungarian algorithm for the optimal assignment problem: Given N workers and M jobs, find a minimal cost assignment of one job to each worker.

## Examples

A synthetic example with a simple solution.

``````# Each worker-job combination has a random cost
cost = rand(4,4)
# However, each worker can do a certain job with zero cost
best_jobs = [3,4,1,2]
for (i,j) in enumerate(best_jobs); cost[i,j] = 0; end

# Compute optimal assignment given the cost
computed_best_jobs = munkres(cost)

@assert best_jobs == computed_best_jobs
``````

Example output:

``````julia> cost = rand(4,4)
4x4 Array{Float64,2}:
0.455632  0.0972016  0.807122  0.806295
0.933324  0.280094   0.261727  0.235289
0.53323   0.408037   0.935853  0.62243
0.08281   0.147279   0.649129  0.910296

julia> best_jobs = [3,4,1,2]
4-element Array{Int64,1}:
3
4
1
2

julia> for (i,j) in enumerate(best_jobs); cost[i,j] = 0; end

julia> computed_best_jobs = munkres(cost)
4-element Array{Int64,1}:
3
4
1
2
``````

10/23/2015