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?