Finding Conditions on Distances With Djikstra’s Algorithm

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

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

Comments are closed.