福特-富尔克森算法
維基百科,自由的 encyclopedia
福特-富尔克森方法(英語:Ford–Fulkerson method),又稱福特-富尔克森算法(Ford–Fulkerson algorithm),是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”,是因为它寻找增广路径的方式并不是完全确定的,而是有几种不同时间复杂度的实现方式[1][2]。它在1956年由小萊斯特·倫道夫·福特及德爾伯特·雷·富爾克森[3]发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法,这是一个特殊的福特-富尔克森算法实现。
算法的思想如下:只要有一条从源点(开始节点)到汇点(结束节点)的路径,在路径的所有边上都有可用容量,就沿着这条路径发送一个流,流量由路径上的最小容量限制。 然后再找到另一条路径,一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。