通常,这对距离和容量没有任何限制,这是最小成本的最大流量问题。
i-can-hold成本为0的接收器。i-have-to-walk。可以使用Ford–Fulkerson算法来找到最大流量,但不考虑成本。尽管可以通过更简单的示例了解流网络,但可能有助于学习。
有许多不同的算法可将成本降至最低。一种是“连续最短路径”。这个想法是反复寻找一条从源到剩余网络中汇入的最小成本路径,并沿着该路径添加流量,直到找不到更多路径为止。
例如:

a)标记每个顶点(成本,容量)的流网络。包含一列3个学生的列,这些列与2个中心的列相连。
b)在剩余网络中沿最短路径(可以在Bellman-Ford中找到)添加的流量。剩余网络是根据可用容量(容量减去各个方向的流量)创建的图形。
c)沿着另一条路径增加了更多的流量。
d)最佳流量。流已沿着更改已添加流的路径添加。这是允许的,因为残余网络在流动的相反方向上具有容量。
也可以看看: