ya something like finding different augmenting paths caluclating the max flow.pls refer coreman.....
On Wed, Sep 30, 2009 at 1:36 PM, Prabhu Hari Dhanapal < [email protected]> wrote: > This is something like a "Flow Network Problem" . > > In the problem , you are just required to push max number of beads to > the receiver - which is the same as Max flow > > The attached file explains some concepts that might help you solve this . > Max flow - min cut theorem , the ford fulkerson algorithm and others > ... > > > > > On Wed, Sep 30, 2009 at 3:46 AM, Miroslav Balaz > <[email protected]>wrote: > >> So at each step you can move any number of beads form some betwwen some >> pairs (in particular more than one) of adjecent vertices? >> >> It seems to be complicated problem. >> IMHO it is about some routing strategy than graph flow. >> If you do reduction to edge capacit, than the maximum flow and longest >> path on the flow will give you an upperbound (longest path+roof(N/max >> flow)-1) >> >> 2009/9/19 MrM <[email protected]> >> >> >>> there is a graph, consisting of N Vertices and some Edges ! >>> each Vertex has a Capacity(for storing Beads), and Capacity of 1st and >>> N-th Vertex is infinite ! >>> there are M Beads in the first Vertex, and we want to move this M >>> Beads to the N-th Vertex with the minimum number of steps ! >>> in each step, we can move some Beads from i-th Vertex to j-th Vertex >>> if and only if there exists an Edge between i-th and j-th Vertex ! >>> the number of Beads at each Vertex cannot exceed its Capacity ! >>> find the minimum number of required steps ! >>> inputs : >>> 1. N 2. adjacency matrix 3. capacity of Vertices [2 ... N-1] >>> 4. M >>> >>> Example : >>> N = 5, >>> adjacency matrix : >>> 0 1 1 0 0 >>> 1 0 0 1 0 >>> 1 0 0 1 0 >>> 0 1 1 0 1 >>> 0 0 0 1 0 >>> capacities : >>> 2-> 2, 3-> 2, 4-> 3 >>> M = 10 >>> Result for example : 6 >>> >>> i will appreciate anyone who write something like Psudo-Code for this >>> problem ! >>> >>> >>> >> >> >> > > > -- > Hari > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
