Algorithm
Development Kit 1.0

algs.model.network
Class ShortestPathArray

java.lang.Object
  extended by algs.model.network.Search
      extended by algs.model.network.ShortestPathArray

public class ShortestPathArray
extends Search

Encapsulate algorithm by which the augmenting path for a Minimal Cost, Maximal Flow network is found.

Use priority queue.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 
Fields inherited from class algs.model.network.Search
BACKWARD, FORWARD, numVertices
 
Constructor Summary
ShortestPathArray(FlowNetwork<EdgeInfo[][]> network)
           
 
Method Summary
 boolean findAugmentingPath(VertexInfo[] vertices)
          Determine whether an augmenting path was found.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ShortestPathArray

public ShortestPathArray(FlowNetwork<EdgeInfo[][]> network)
See Also:
Search.Search(FlowNetwork)
Method Detail

findAugmentingPath

public boolean findAugmentingPath(VertexInfo[] vertices)
Determine whether an augmenting path was found. If the sink Index has a non-infinite distance, then some augmenting path was indeed found.

Specified by:
findAugmentingPath in class Search
Parameters:
vertices - initially an empty array of Vertex Info; afterwards, contains the path which can be determined by traversing backwards from the sink index.
Returns:
true if an augmented path was located; false otherwise.
See Also:
Search.findAugmentingPath(VertexInfo[])

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.