CHALLENGE: Route Finding

[Banfa]

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?

[JosAH]

Nah, that's an MCNF (Minimal Cost Network Flow) problem (cost on nodes and
edges). Does a book reference count?

kind regards,

Jos

[Banfa]

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

[JosAH]

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*

[jkmyoung]

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.

[mofmans2ndcoming]

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?