The shortest path problem can be described on the transport network:
1.) transport network has n hubs, where 1is starting point and hub n is destination point.
2.) near by hubs are connected with the links with positive distances
3.)you need to choose the shortest path between the starting and ending point.
For example lets choose the shortest path from Verona to Carrara using the motorway only.!
Here is scheme.
And the distances are given in the next table:
Next step is to look at the hubs. Every hub has the links who are entering and exiting.
Those links who are exiting the hub are + those who are entering are - , and the last parameter is that the starting point has value 1 and the ending point has the value -1.
Now for every hum you need to calculate the entering and exiting links.
x1,2 + x1,3 + x1,5 = 1 (hub 1)
x2,4 – x1,2 = 0 (hub2)
x3,6 – x1,3 = 0 (hub 3)
x4,8 – x2,4 – x5,4 = 0 (hub 4)
x5,4 + x5,6 – x1,5 = 0 (hub 5)
x6,7 – x3,6 – x5,6 = 0 (hub 6)
x7,8 – x6,7 = 0 (hub 7)
– x4,8 – x7,8 = – 1 (hub 8)
In excel you need to enter the calculations for hubs which you made the step before. Fore every link.
Then you can turn on solver and make the conditions:
You need to choose min (we are searching for minimum path distance) and you chooose the function (it is sum from hubs and ye/no conditions). Yes/no means if that link is chosen or not, it need to be binary. First hub has value 1 last -1.
And the solving method is simplex.
Now when you click solve you will get the minimum path distance . And where are 1 in the conditions yes/no that are the chosen links. It is: 1-5, 4-8, 5-4.
So the result is:
YOu can see in the google maps that problem solved:
Photo soruce: googlemaps
