计算最小的 - 切在向加权图使用maxflow算法 [英] calculating minimum - cut in a directed weighted graph using maxflow algorithm

问题描述

我一直使用福特Fulkerson算法计算出的最大流量，现在我要实现项目的选择问题，我需要计算最大。没有。可行的设计项目需要找到不包含一个min.cut。可行的项目，最大的利润。 应该用什么算法来找到分钟。切*知道max.flow在图形之后。我*如何使用最大流量来确定切割含有即没有。节点有助于最大flow.I的需要选择最优节点集，使得收入maximisied。在我的申请的每个节点都与一个相关联的收入，也可以是正和负也。并有precedence限制也eg.if一个选择比B和？C也必须选择可有人告诉我如何实现这种

i have calculated maximum flow using ford fulkerson algorithm,now i want to implement project selection problem for which i need to calculate max. no. of feasible projects.i need to find a min.cut containing no. of feasible projects with max profit. What should be the algorithm to find a min. cut *after knowing max.flow in graph.*How can i use max flow to determine cut containing i.e no. of nodes contributing to max flow.I need to select the optimal set of nodes so that revenue is maximisied. In my application each node is associated with a revenue,it can be positive and negative also. and there are precedence constraints also,eg.if a is selected than b&c also must be selected Can anybody tell me how to implement this?

我在最大流量曲线图把它改造为：如果收入（节点）> 0从源头>节点添加其他边缘从添加的于节点边缘>水槽和我已经创造了无限容量为$ P A EGDE $ pcedence限制

I have transformed it in max flow graph as follows: if revenue(node)>0 add an edge from source->node else add an edge from node->sink and i have created a egde of infinite capacity for precedence constraints

推荐答案

我们可以从源顶点运行DFS / BFS，然后找到饱和计算min.cut（A，B） 在最终的剩余图ieafter没有增广路径边

we can calculate min.cut (A,B)by running dfs/bfs from source vertex, and then finding the saturated edges in final residual graph i.e.after there are no augmenting paths

这篇关于计算最小的 - 切在向加权图使用maxflow算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！