I notice from your data that it is longer and more expensive to go from 4 to 3 than it is to go from 3 to 4.

And you can't even get to 2! (Did you know that you can buy train tickets in England for train stations that don't exist! Cool!).

This is a sort of pseudo-code.

Might give you enough pointers to work with. I am sure someone will supply the complete answer though!

// Psuedo code.

// An index of source+destination may make speedier access?

$aRouteSteps[];

$aRouteDistances[];

$iCurrentDistance = 0;

$iShortestDistance = 99999;

$aShortestRouteSteps[];

$iSteps = 0;

$StartCityID = 0;

$EndCityID = 0;

select $StartCity,$EndCity in source+destination.

if found, then this SHOULD be the shortest route! If not, then the data is wrong!

if not found then you need to start at the $StartCity and follow all valid links out from the $StartCity.

As you jump from each city to city you store the distance and the route so far.

You do NOT include cities that have already been used.

You add the distance to the total distance.

When you get to the $EndCity, if the total distance is less than the shortest distance, then you store that info in the Shortest... fields.

This is like a tree recursion. Rather than walking a web (i.e. links to places we have already been), we simply ignore them if we have already visited them.

We also stop when we reach the end.

TreeWalk(CurrentLocation)

{

Is this location the EndCity?

Yes

Is the current distance less than the last total distance

Yes

Store the current information in the shortest... fields.

Exit this recursion.

Loop through all destinations for this location

Has destination already been visited on the route?

No

Store the step and values;

Increment the step counter;

Call TreeWalk(Destination);

}