445,758 Members | 1,225 Online
Need help? Post your question and get tips & solutions from a community of 445,758 IT Pros & Developers. It's quick & easy.

# CHALLENGE: Route Finding

Expert Mod 5K+
P: 8,916
Attached is a map of the Scriptsville Metro.

Produce an algorithm that given a starting station and a finishing station will produce 2 routes:

1. The route that passes through the fewest stations
2. The route that requires the fewest number of transfers but otherwise passes through the fewest number of stations

Given that it takes 5 minutes to travel between each station and transfering also takes 5 minutes for each route give the following output

1. Starting Station
2. Finishing Station
3. Each station at which you need to transfer
4. Total number of stations visited inclusive of the starting and finish stations
5. Total number of transfers made
6. Total time for the journey

Use any language or package you like to solve this problem (VB, pseudo code, C/C++, SQL, Python etc), +kudos to anyone producing a Prologue solution.

Yoursolution should

1. Indicate the data structures used to encode the map for the computer
2. Provide the algorithm to operate on this data to produce the required results.

Further Questions

For any possible configuration of a multilined metro system is it guaranteed that one of the 2 routes produced by your algorithm will be the quickest for all possible journeys?

For the metro system in the map is it guaranteed that one of the 2 routes produced by your algorithm will be the quickest for all possible journeys?
Attached Files
 ScriptsvilleMetro.zip (26.0 KB, 256 views)
Oct 5 '07 #1
5 Replies

 Expert 10K+ P: 11,448 Nah, that's an MCNF (Minimal Cost Network Flow) problem (cost on nodes and edges). Does a book reference count? kind regards, Jos Oct 5 '07 #2

 Expert Mod 5K+ P: 8,916 Nah, that's an MCNF (Minimal Cost Network Flow) problem (cost on nodes and edges). Does a book reference count? With the utmost respect Jos, if it isn't a challenge for you then there is no need to attempt it :p You could of course set your own :D Oct 5 '07 #3

 Expert 10K+ P: 11,448 With the utmost respect Jos, if it isn't a challenge for you then there is no need to attempt it :p You could of course set your own :D I'd like to propose the following silly problem as a contestant: http://www.thescripts.com/forum/thread717662.html No arrays allowed (and no more advanced containers either ;-) The resulting program will be a highly convoluted, obfuscated thingy, no doubt about about it. I'm no game when it comes to those stinky operations research like problems such as your proposed MCNF thingy; I even don't dare to tell my old mom that I deal with those monsters on a daily basis; I feel so ashamed; so .. so .. smeared ;-) kind regards, Jos *sob* Oct 5 '07 #4

 Expert 100+ P: 2,057 For any possible configuration of a multilined metro system is it guaranteed that one of the 2 routes produced by your algorithm will be the quickest for all possible journeys? With the configuration given, I think it is the case. However the answer is no in general. For example take the configuration 1-2-3-4-5-6-7-8-9-10-11-12 Assume there is a train that goes all the way from 1-12 Also assume there are trains 1-4, 4-7, 7-10 10-12 1-3-6 6-9-12 The route with the least number of stations is 1,4,7,10.12 (3 transfers) However, this takes 7X5 = 35 mins The route with the least number of transfers is 1,2,3,4,5,6,7,8,9,10,11,12 (0 transfers) 11 X 5 = 55 mins Fastest route 1,3,6,9,12 (1 transfer) 5X5 = 25 mins. Oct 5 '07 #5

 P: 16 I'd like to propose the following silly problem as a contestant: http://www.thescripts.com/forum/thread717662.html No arrays allowed (and no more advanced containers either ;-) What if you use LISP? Nov 18 '07 #6