edu.princeton.cs.algs4

## Class AssignmentProblem

• Object
• edu.princeton.cs.algs4.AssignmentProblem

• ```public class AssignmentProblem
extends Object```
The `AssignmentProblem` class represents a data type for computing an optimal solution to an n-by-n assignment 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.

This computes correct results if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 252.

For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor and Description
`AssignmentProblem(double[][] weight)`
Determines an optimal solution to the assignment problem.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`double` `dualCol(int j)`
Returns the dual optimal value for the specified column.
`double` `dualRow(int i)`
Returns the dual optimal value for the specified row.
`static void` `main(String[] args)`
Unit tests the `AssignmentProblem` data type.
`int` `sol(int i)`
Returns the column associated with the specified row in the optimal solution.
`double` `weight()`
Returns the total weight of the optimal solution
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### AssignmentProblem

`public AssignmentProblem(double[][] weight)`
Determines an optimal solution to the assignment problem.
Parameters:
`weight` - the n-by-n matrix of weights
Throws:
`IllegalArgumentException` - unless all weights are nonnegative
`IllegalArgumentException` - if `weight` is `null`
• ### Method Detail

• #### dualRow

`public double dualRow(int i)`
Returns the dual optimal value for the specified row.
Parameters:
`i` - the row index
Returns:
the dual optimal value for row `i`
Throws:
`IllegalArgumentException` - unless `0 <= i < n`
• #### dualCol

`public double dualCol(int j)`
Returns the dual optimal value for the specified column.
Parameters:
`j` - the column index
Returns:
the dual optimal value for column `j`
Throws:
`IllegalArgumentException` - unless `0 <= j < n`
• #### sol

`public int sol(int i)`
Returns the column associated with the specified row in the optimal solution.
Parameters:
`i` - the row index
Returns:
the column matched to row `i` in the optimal solution
Throws:
`IllegalArgumentException` - unless `0 <= i < n`
• #### weight

`public double weight()`
Returns the total weight of the optimal solution
Returns:
the total weight of the optimal solution
• #### main

`public static void main(String[] args)`
Unit tests 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.
Parameters:
`args` - the command-line arguments