相关算法

Goldberg和Tarjan（1986）提出的压入与重标记算法将性能提升到O(V*E*log(V2/E))，并且能够并行化获得更大的性能提升。最大流问题的一个变种，又名多重物资流问题，泛化之后就是最大流问题。简单地说，这种问题就是一个有着多重源点和汇点的网络，并且在不同源点和汇点之间运输不同的物资，而不是像最大流问题中，仅仅只有一个源点和一个汇点。尽管边的容量是固定的，但是每对汇点和源点的使用需求并不一样。现实中，这种算法的应用于无线网中的路由问题（Fragouli和Tabet，2006）。Leighton和Rao撰写过一篇文章（1999），这篇文章被大量的多重物资流问题所引用。

最大流的一些简单变种如下：

顶点容量

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

如果流网络中的每个顶点v都有一个最大容量k(v)将会怎么样呢？构建一个修改过的图G'。对于网络中的每个顶点v，构建两个顶点v'和v"。并且创建一条边(v",v')，这条边的容量是k(v)。在图G中创建一条容量为c(x,v)的边（x,v），对应原始图G中的容量为c(x,v)的每条边（x,v"）。对应着原始图G中的每条边（v,w），在G'中创建一条新边（v',w），其容量为k(v)。解出G'也就得到了G的解。

无向边

如果流网络G是无向边，那么会怎么样呢？构建一个流网络G'。在新图中，所有的顶点都一样，对应着原始图中容量为c(u,v)的边（u,v），在G'中构建一对新边（u,v）和（v,u），每条边的容量都为c(u,v)。G'的解也就是G的解。