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