首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》相关算法

关灯直达底部

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

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

顶点容量

如果流网络中的每个顶点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的解。