Finding Conditions on Unknown Distances for a Network
Using Djikstr's algorithm we can find the least distance from one point to another in a network. If the network contains unknown distances however, and we know which is the shortest route, we may be able to find conditions on the unknown length.
The network below contains the unknown distance
Suppose we know that the shortest route from A to F is ABDF. The route ABDF is
The distance ABCDF is 6 so
The distance ABEF is 6 so
The distance ABCEF is 7 so
The distance ACEF is 7 so
The distance ACDF is 6 so
The distance ACBDF iswhich is always true and tells us nothing.
The distance ACEDF is 11 so
The distance ABDEF is 8+x so
Inspection of all this inequalities leads us to the conclusion thatof course so that