| AssignmentProblem Class |
The AssignmentProblem class represents a data type for computing an optimal solution to an N-by-NAssignment problem. The assignment problem is to find a minimum weight matching in an edge-weighted complete bipartite graph.
The data type supplies methods for determining the optimal solution and the corresponding dual solution.
This implementation uses the Successive shortest paths algorithm. The order of growth of the running time in the worst case is O(N^3 log N) to solve an N-by-N instance.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class AssignmentProblem
The AssignmentProblem type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | AssignmentProblem |
Determines an optimal solution to the assignment problem.
|
Methods| Name | Description | |
|---|---|---|
| DualCol |
Returns the dual optimal value for the specified column. |
| DualRow |
Returns the dual optimal value for the specified row. |
 | MainTest |
Demo test the AssignmentProblem data type.
Takes a command-line argument N; creates a random N-by-N matrix;
solves the N-by-N assignment problem; and prints the optimal
solution. |
| Sol |
Returns the column associated with the specified row in the optimal solution. |
| Weight |
Returns the total weight of the optimal solution |
RemarksFor additional documentation, see Section 6.5Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
This class is a C# port from the original Java class AssignmentProblem implementation by the respective authors.
See Also