i think steiner tree can be used On Sep 26, 10:05 pm, drealecs <dreal...@gmail.com> wrote: > I have a software problem and I'm searching for a solution but tried > different algorithm approach and nothing came out. > I'm not very familiar with all the graph algorithms and I hope there > is already a way to solve this kind of problems in polynomial time. > > I need the algorithm for different task but I illustrated simple like > this: > > The are N cities and there is a wanderer. > The time it takes for him to go from a town to another town is known - > Txy (from town x to town y). > From any town he can go to another town so it is a complete graph. > In each town there is a an amount of money Mx the wanderer wants to > collect. > It isn't enough time to pass through all cities. > Having the total available time T and the starting point i, the > problem is to find the best route so that the money he collects will > be maximum. > > Input numbers range: > N is between 400 and 600 > Mx(M1, M2, ...) are between 50 and 500, x between 1 and N > Txy are between 1 and 200, x and y are between 1 and N, x!=y > T is between 1000 and 5000 > > The problems is shared > here:http://www.evernote.com/shard/s119/sh/79f47a65-c1e6-44da-bbc0-7d10e36... > > Thanks
-- 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?hl=en.