MinCost MaxFlow with [Undirected Graph]

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

MinCost MaxFlow with [Undirected Graph]

Post by hank » Thu Oct 20, 2005 7:14 am

Hello, everybody

I know the method to find the minimum cost maximum flow in a directed grapth.

But how to find
MinCost MaxFlow with an "Undirected" Graph ?

I also see the online judge problem "10594 DataFlow"
the graph in that problem also is undirected.

( I need a simple algorithm , not too difficult. )

:D


Thanks in advance.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: MinCost MaxFlow with [Undirected Graph]

Post by misof » Thu Oct 20, 2005 9:53 am

hank wrote:Hello, everybody

I know the method to find the minimum cost maximum flow in a directed grapth.

But how to find
MinCost MaxFlow with an "Undirected" Graph ?

I also see the online judge problem "10594 DataFlow"
the graph in that problem also is undirected.

( I need a simple algorithm , not too difficult. )

:D


Thanks in advance.
Simply replace each undirected edge by a pair of directed edges, each of them having the same capacity and length/cost.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Thu Oct 20, 2005 10:24 am

Hi, misof

Thanks for your help.

But are you sure the method is correct ?

your method seems to be right only in MaxFlow problem , not in MaxFlowMinCost problem.

( I am not sure ... maybe I am wrong )

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Oct 20, 2005 12:29 pm

Well, for positive edge lengths/costs it should work. Consider a pair of twin edges (an edge from A to B and an edge from B to A). Clearly if there is a positive flow on both of them we can cancel a part of it. This doesn't alter the size of the flow and it lowers its cost. Therefore in an optimal solution at most one of these edges has a positive flow, which exactly corresponds to the undirected case.

Post Reply

Return to “Algorithms”