网络流四种主流算法时间复杂度分析

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了网络流四种主流算法时间复杂度分析，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3028字，纯文字阅读大概需要5分钟。

内容图文

权威分析各种实现网络流算法的时间复杂度

简单总结 

FF算法： 利用dfs实现，时间复杂度O（V*E^2）

EK算法：利用bfs实现，时间复杂度O（V*E^2）

Dinic算法：递归实现，时间复杂度O（V^2*E）

SAP算法：时间复杂度O（V^2*E）但是加上弧优化和间隙优化之后时间复杂度非常可观

由于一般边数>>顶点数，所以后面两个算法时间复杂度优势很大

而由于递归，时间复杂度上SAP优于Dinic

因此小数据（水）的时候使用Dinic，大数据的时候还是用SAP

排名SAP > Dinic > EK ≈ FF，所以学了EK就不学FF了，但是SAP和Dinic都要学！

Method	Complexity	Description
Linear programming		Constraints given by the definition of a legal flow. See the linear program here.
Ford–Fulkerson algorithm	O(Emax|f|)	As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path. The algorithm is only guaranteed to terminate if all weights are rational. Otherwise it is possible that the algorithm will not converge to the maximum value. However, if the algorithm terminates, it is guaranteed to find the maximum value.
Edmonds–Karp algorithm	O(VE2)	A specialization of Ford–Fulkerson, finding augmenting paths with breadth-first search.
Dinic's blocking flow algorithm	O(V2E)	In each phase the algorithms builds a layered graph with breadth-first search on the residual graph. The maximum flow in a layered graph can be calculated in O(VE) time, and the maximum number of the phases is n-1. In networks with unit capacities, Dinic's algorithm terminates in  time.
MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm	O(V3)	Only works on acyclic networks. Refer to the Original Paper.
Dinic's algorithm	O(VElog(V))	The dynamic trees data structure speeds up the maximum flow computation in the layered graph to O(V E log(V)).
General push-relabel maximum flow algorithm	O(V2E)	The push relabel algorithm maintains a preflow, i.e. a flow function with the possibility of excess in the vertices. The algorithm runs while there is a vertex with positive excess, i.e. an active vertex in the graph. The push operation increases the flow on a residual edge, and a height function on the vertices controls which residual edges can be pushed. The height function is changed with a relabel operation. The proper definitions of these operations guarantee that the resulting flow function is a maximum flow.
Push-relabel algorithm with?FIFO?vertex selection rule	O(V3))	Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations until the excess is positive or there are admissible residual edges from this vertex.
Push-relabel algorithm with dynamic trees		The algorithm builds limited size trees on the residual graph regarding to height function. These trees provide multilevel push operations.
KRT (King, Rao, Tarjan)'s algorithm
Binary blocking flow algorithm		The value U corresponds to the maximum capacity of the network.
James B Orlin's + KRT (King, Rao, Tarjan)'s algorithm		Orlin's algorithm solves max-flow in O(VE) time for  while KRT solves it in O(VE) for .

内容总结

以上是互联网集市为您收集整理的网络流四种主流算法时间复杂度分析全部内容，希望文章能够帮你解决网络流四种主流算法时间复杂度分析所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---