public class HungarianAlgorithm extends Object
An assignment for a cost matrix that has more workers than jobs will necessarily include unassigned workers, indicated by an assignment value of -1; in no other circumstance will there be unassigned workers. Similarly, an assignment for a cost matrix that has more jobs than workers will necessarily include unassigned jobs; in no other circumstance will there be unassigned jobs. For completeness, an assignment for a square cost matrix will give exactly one unique worker to each job.
This version of the Hungarian algorithm runs in time O(n^3), where n is the maximum among the number of workers and the number of jobs.
Constructor and Description |
---|
HungarianAlgorithm(double[][] costMatrix)
Construct an instance of the algorithm.
|
public HungarianAlgorithm(double[][] costMatrix)
costMatrix
- the cost matrix, where matrix[i][j] holds the cost of assigning
worker i to job j, for all i, j. The cost matrix must not be
irregular in the sense that all rows must be the same length.Copyright (C) 2016-2018 Benjamin Paaßen, AG Theoretical Computer Science, Centre of Excellence Cognitive Interaction Technology (CITEC), University of Bielefeld, licensed under the AGPL v. 3: http://openresearch.cit-ec.de/projects/tcs . This documentation is licensed under the conditions of CC-BY-SA 4.0: https://creativecommons.org/licenses/by-sa/4.0/