Java Program

Assignment #4 (80 Points) 

Due: April 18, 2013 (at the beginning of class)

Problem Description

Write a java program that will implement the maximum flow problem discussed in class. The

program should read itsinput from a text file. The input will be in the form of an n x n matrix,

where n isthe number of nodesin the network. Specifically, input will consist of n lines where

each line has a collection of n integers, with each pair of integers separated by a single space.

The value in the i

th row and the j

th column of the matrix represents the capacity of the

connection from the i

th node to the j

th node. A value of -1 indicatesthat there is no link from

node ito node j. Note thatthematrix represents a directed network.

The output of the program should be the maximum flow that can be produced by the input

network. This can be computed from the sum of the outgoing flows from the source or the

incoming flows of the sink. The first node will be the network’ssource, and the last node will

be the network’ssink.

Sample Input

-1 4 2 1 -1 

-1 -1 1 -1 2 

-1 -1 -1 1 2 

-1 -1 -1 -1 3 

-1 -1 -1 -1 -1 

SampleOutput

The outputto the programshould be themaximumflow, 6.

Submission

Submit your assignment through Blackboard. If your assignment contains multiple files, zip

theminto a single folder before submitting.

Notes

Points can be deducted from your assignment based on the quality of its presentation.

Handwritten assignments will not be accepted.