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

Add comment

Security code