All possible subsets of 10 elements is B(100,10), which is over 17 trillion. Not a great algorithm.
You can do this by constructing sets S_0, S_1, S_2, ... S_10, S_11 of stations accessible from the start in 0,1,2,...10, 11 hops. The 11th is from the final station to the destination. It's simple to construct S_i+1 from S_i. I'll leave it to you. For each element of each S_i it's also straightforward to keep track of the min of the max distance that had to be traversed to get to there and a backward pointer to the previous station on the best path. (A bit of care is needed for the case where there's a cycle in the path. In this case a city may have two or more predecessors!) After you've constructed S_11, look for the destination there. If you find it, read off the path in reverse using the back pointers. If it's not there, there exists no path of length 10. If this sounds like Dijkstra's shortest path to you, you're onto something. It's pretty close except that the concrete length of 10 simplifies things. If you are interested in paths with fewer than 10 stations, that's a simple modification I'll also leave to you. On Sep 16, 8:22 pm, pankaj kumar <[email protected]> wrote: > You are given two end points ( consider them as two end stations > at some distance ) there are 100 stations between these two . Now you > need to build a train track between these two end points which > includes only 10 stations and not more than that . Now the objective > is to find such 10 stations such that the maximum distance between any > two consecutive stations is minimum . > > mine solution is > > find all possible subset of 10 elements and answer is that subset > for which sum (of distance between > consecutive stations )is minimum.. > is it correct or any other solution. -- 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?hl=en.
