edu.princeton.cs.algorithms

Class AssignmentProblem

java.lang.Object

edu.princeton.cs.algorithms.AssignmentProblem

public class AssignmentProblem
extends Object

Compilation: javac AssignmentProblem.java Execution: java AssignmentProblem N Dependencies: DijkstraSP.java DirectedEdge.java Solve an N-by-N assignment problem in N^3 log N time using the successive shortest path algorithm. Remark: could use dense version of Dijsktra's algorithm for improved theoretical efficiency of N^3, but it doesn't seem to help in practice. Assumes N-by-N cost matrix is nonnegative.

Constructor Summary

Constructors

Constructor and Description
AssignmentProblem(double[][] weight)

Method Summary

Methods

Modifier and Type	Method and Description
double	dualCol(int j)
double	dualRow(int i)
static void	main(String[] args)
int	sol(int i)
double	weight()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AssignmentProblem

public AssignmentProblem(double[][] weight)

Method Detail

dualRow

public double dualRow(int i)

dualCol

public double dualCol(int j)

weight

public double weight()

sol

public int sol(int i)

main

public static void main(String[] args)