解决最大流问题并不能帮助我们立刻解决本章之前讨论的其他问题。但是，从最大流问题的解决出发，我们去考虑一类相似的问题，这类问题都是在流网络中寻找最大流以及最小化开销。如果我们将网络中的每条边（u,v）赋一个开销d(u,v)表示在此边上运输一个单位的开销，那么目标就是最小化：
∑f(u,v)*d(u,v)
现在，在Ford-Fulkerson算法中，我们强调寻找能够增大网络中流量的增广路的重要性。如果我们修改搜索方法，寻找最小开销的增广路会发生什么呢？我们已经讨论过一些贪心算法（例如第6章中构造最小生成树的Prim算法）就是不断地选择最小开销的方向进行扩展，也许这样的方法能够在这里可行。
为了寻找最小开销的增广路，我们就不能拘泥于单纯使用广度优先搜索或者是深度优先搜索。正如我们在Prim算法中所看到的那样，我们必须要使用一个优先队列来存储和计算流网络中，每个顶点到源点的距离。我们会计算从源点到每一个顶点运输一个单位的开销，然后我们需要在不断的计算过程中维护一个优先队列。随着搜索的进行，优先队列存储着节点的有序集合，这个集合中的元素将会指导着搜索进行的方向。从优先队列中取出到源点距离（这里是开销）最小的顶点u，然后选择一个还未被访问的邻接顶点v，并且满足（a）前向边（u,v）还有多余的容量可供扩展，或者（b）后向边（v,u）的流可以减少，继续进行搜索。如果我们在搜索的过程中遇到了汇点，那么搜索就可以终止，而且成功地找到一条增广路，否则，不存在这样的增广路。例8-6是ShortestPathArray的Java实现。
例8-6：Ford-Fulkerson寻找最短路径（以开销计算）
使用这样的策略来寻找最小开销的增广路，我们可以解决图8-1的剩余问题。在图8-7中我们使用一个小例子来比较一个最大流计算和最小开销流计算，从中可以看到这个最小开销搜索策略的高效了。图的底部是每种方法找到的最大流。
在这个例子中，你是负责两家工厂的船务经理，这两家工厂一家在芝加哥（v1），另一家在华盛顿特区（v2），每家工厂每天能够生产300件工具。你必须保证在休斯敦（v3）和波士顿（v4）的消费者每天能够有300件工具供应。你有一些选择策略，如图8-7所示。例如，在华盛顿特区和休斯敦之间每天运输280件工具，每件工具花费4美元，但是如果你从华盛顿特区运到波士顿，开销会增至6美元（虽然在这条航路每天可以运送350件工具）。
图 8-7 揭示最小开销搜索策略的高效我们不清楚Ford-Fulkerson算法是否可以用来解决这个问题，但是我们能够构造一个图G，有一个源点s0，连接两个工厂顶点（v1和v2）以及有一个新的汇点t5，连接两个消费顶点（v3和v4）。在图8-7的左边我们使用Edmonds-Karp来证明我们能够满足消费者的所有需求，但是每天的运输费用是3600美元。为了节省空间，源点和汇点都被忽略了。在Ford-Fulkerson的每次迭代中，增广路的影响（当一次迭代更新了边的流，流的值标记为灰色）显而易见。
我们能够得到最小开销吗？在图8-7的右边，我们给出了使用ShortestPathArray作为搜索策略的Ford-Fulkerson算法执行过程。我们可以看到第一条增广路的寻找过程是如何利用最低开销的航运率。同样ShortestPathArray使用了开销最高昂的路径，即从芝加哥（v1）到休斯敦（v3）的路，因为没有其他的路可以满足用户的需求，事实上，如果这种情况发生，我们将会看到增广路减少了从华盛顿特区（v2）和到休斯敦（v3）、波士顿（v4）之间的流。