Ford-Fulkerson算法是一种用于计算网络流中最大流的迭代方法。它通过反复寻找增广路径并增加路径上的流量,直到无法找到更多的增广路径为止。
Ford-Fulkerson算法是一种用于解决网络流问题中最大流问题的经典算法,由L. R. Ford Jr.和D. R. Fulkerson于1956年提出。最大流问题是指在一个有向图中,给定源点(source)和汇点(sink),求从源点到汇点的最大可能流量。算法基于增广路径(augmenting path)的概念,通过不断寻找并增加流量直到无法找到更多增广路径为止。
假设有一个流网络,包含6个节点(0-5),其中0为源点,5为汇点,边的容量关系如下:
...