Free Professional Development

Or

Author:
Nazmul Bashar

We will be able to work out the shortest distance between two points in a network.

We will be able to use Dijkstra's Algorithm to find the shortest distance.

Dijkstra method is not the only way to work out the shortest path between two nodes (points) in the network. This is more formal and methodical. Practically this method does not require any Mathematics. It is expected, when you finish watching the video, that you take down important points. Especially, the step by step procedure is given in one of the slides. Please make your own personal note, either on Google Doc or on your notebook.

Tutorial

In 1962, a Chinese mathematician called Kuan Mei-Ko was

interested in a postman delivering mail to a number of streets

such that the total distance walked by the postman was as short

as possible. How could the postman ensure that the distance

walked was a minimum?

In the following example a postman has to start at A, walk along

all 13 streets and return to A. The numbers on each edge

represent the length, in metres, of each street. The problem is to

find a trail that uses all the edges of a graph with minimum

length.

Source: http://goo.gl/DWI1hZ