[algogeeks] Re: Find all paths from every member of set of vertices(V1) to every member of other set of vertices(V2) V1 ^ V2 = 0

Sun, 20 Aug 2006 09:47:20 -0700



On 8/20/06, ridvansg <[EMAIL PROTECTED]> wrote:

Hi all,
I have this task to solve:
Given a weighted directed Graph G(V,E) with weights  w(u,v).  u, v   -
elements of  V.
If v(i, j) is element of V then v(j,i) is not.

For each  vi Element of V are defined:
      Sum of weights of incoming edges: Income(i)
      Sum of weights of outgoing edges: Outgo(i)
       The balance of the node: Balance(i) = Income(i) - Outgo(i).

       An vertice is called positive or negative depending  on it's
balance.
I am given set of negative vertices : VBadPayers ( not all negative
vertices)

What does the above sentence mean? 

I will call the set of all positive vertices VTakers.

Imagine edges to be duties. Vertices with negative balances are payers
and edges with positive balances are takers.
Imagine all vertices from V1 to be badpayers.

The task is to reduce balances of all the takers with balances of all
the bad payers. The balances of good payers should stay not changed.

The reducement should be proportional to the sum of weights of all the
paths from a given badpayer to a given taker.

Please make the problem statement more abstract  (i.e) as sum of weights and edges and not as balances and duties

Enjoy:)
Ridvan




--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to