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 <maleki...@gmail.com> > > 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 ! > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
