Algorithms in a Nutshell

(^244) | Chapter 8: Network Flow Algorithms
Armed with this strategy for locating the lowest-cost augmenting path, we can
solve the remaining problems shown in Figure 8-1. To show the effect of this low-
cost search strategy, we show in Figure 8-7 the side-by-side computation on a
small example comparing a straightforward Maximum Flow computation with a
Minimum Cost Flow computation. Each iteration moving vertically down the
figure is another pass through thewhileloop within thecompute( )method of
FORD-FULKERSON(as seen in Example 8-1). The result, at the bottom of the
figure, is the maximum flow found by each approach.
In this example, you are the shipping manager in charge of two factories in
Chicago (v 1 ) and Washington, D.C. (v 2 ) that can each produce 300 widgets daily.
You must ensure that two customers in Houston (v 3 ) and Boston (v 4 ) each receive
300 widgets a day. You have several options for shipping, as shown in the figure.
For example, between Washington, D.C. and Houston, you may ship up to 280
widgets daily at $4 per widget, but the cost increases to $6 per widget if you ship
from Washington, D.C. to Boston (although you can then send up to 350 widgets
per day along that route).
It may not even be clear that FORD-FULKERSONcan be used to solve this
problem, but note that we can create a graphGwith a new source vertexs 0 that
connects to the two factory nodes (v 1 andv 2 ) and the two customers (v 3 andv 4 )
connect to a new sink vertext 5. On the lefthand side of Figure 8-7 we execute the
EDMONDS-KARPvariation to demonstrate that we can meet all of our customer
needs as requested, at the total daily shipping cost of $3,600. To save space, the
source and sink verticess 0 andt 5 are omitted. During each of the four iterations
by FORD-FULKERSON, the impact of the augmented path is shown (when an iter-
ation updates the flow for an edge, the flow value is shaded gray).
Is this the lowest cost we can achieve? On the righthand side of Figure 8-7 we
show the execution of FORD-FULKERSONusingShortestPathArrayas the search
strategy, as described in Example 8-6. Note how the first augmented path found
takes advantage of the lowest-cost shipping rate. AlsoShortestPathArrayonly
uses the costliest shipping route from Chicago (v 1 ) to Houston (v 3 ) when there is
dist[v] = newDist;
if (inqueue[v]) {
pq.decreaseKey(v, newDist);
} else {
pq.insert(v, newDist);
inqueue[v] = true;
}
}
}
}
}
return dist[sinkIndex] != Integer.MAX_VALUE;
}
Example 8-6. Shortest path (in costs) search for Ford-Fulkerson (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use
Licensed by
Ming Yi