By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,758 Members | 1,225 Online
Bytes IT Community
+ Ask a Question
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

Banfa
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
File Type: zip ScriptsvilleMetro.zip (26.0 KB, 256 views)
Oct 5 '07 #1
Share this Question
Share on Google+
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

Banfa
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

jkmyoung
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

Post your reply

Sign in to post your reply or Sign up for a free account.