Loading AI tools
来自维基百科,自由的百科全书
在优化理论中,最大流问题(英语:Maximum flow problem)涉及到在一个单源点、单汇点的网络流中找到一条最大的流。
最大流问题可以被看作是一个更复杂的网络流问题(循环问题,circulation problem)的特殊情况。s-t流(从源点s到汇点t)的最大值等于s-t割的最小容量,这被称为最大流最小割定理。
最大流问题最早是在1954年由泰德·哈里斯和F·S·罗斯(F. S. Ross)通过一个苏联铁路的交通流量的简化模型提出的。[1][2][3] 1955年,小莱斯特·伦道夫·福特和德尔伯特·雷·富尔克森创建了第一个已知的算法,福特-富尔克森算法。[4][5]
多年来,最大流问题的各种改进算法被发现,例如杰克·埃德蒙兹、理查德·卡普和叶菲姆·迪尼茨的最短增广路算法;迪尼茨的阻塞流算法;安德鲁·V·戈德堡和罗伯特·塔扬的Push-Relabel算法;戈德堡和Rao的binary阻塞流算法;Christiano、Kelner和亚历山大·马德瑞(Aleksander Madry)的电流算法;Spielman发现一个最大流近似最优解,但仅适用于无向图。[6][7]
设为一个网络,其中和分别是的源点和汇点()。
算法 | 复杂度 | 描述 |
---|---|---|
线性规划 | ||
福特-富尔克森算法 | O(E max| f |) | |
埃德蒙兹-卡普算法 | O(VE2) | 福特-富尔克森算法的特例,使用广度优先搜索寻找增广路径. |
迪尼茨阻塞流算法 | O(V2E) | |
MPM (Malhotra, Pramodh-Kumar and Maheshwari)算法[8] | O(V3) | 只适用于无环图。参考 Original Paper. |
Dinic算法 | O(VE log(V)) | |
push-relabel maximum flow算法 | O(V2E) | |
Push-relabel算法,使用FIFO vertex selection rule | O(V3) | |
Push-relabel算法,使用 dynamic trees | ||
KRT (King, Rao, Tarjan)算法[9] | ||
Binary阻塞流算法[10] | ||
James B Orlin's + KRT (King, Rao, Tarjan)算法[11] | Orlin's algorithm (页面存档备份,存于互联网档案馆) solves max-flow in O(VE) time for while KRT solves it in O(VE) for . |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.