对于最大流量问题,似乎有许多非常复杂的算法,至少有一种算法是在去年才开发出来的。Orlin 的Max 在 O(mn) 时间或更短的时间内流动,给出了在 O(VE) 中运行的算法。
另一方面,我最常看到实现的算法是(我并没有声称已经进行了详尽的搜索;这只是偶然的观察):
- 埃德蒙兹-卡普,O(VE^2)
- Push-relabel, O(V^2 E), or O(V^3) 使用 FIFO 顶点选择
- Dinic 算法,O(V^2 E)
具有更好渐近运行时间的算法对于现实世界中的问题规模是否不实用?另外,我看到很多算法都涉及“动态树”;这些曾经在实践中使用过吗?