Figure 2 represents a network of roads in Kolhumadulu Thimar

Figure 2 represents a network of roads, in Kolhumadulu Thimarafushi. The number on each arc is the length, in m, of the corresponding road. (a) Use Dijkstra?s algorithm to find the shortest route from A to J. State the shortest route and its length. (b) Explain how you determined the shortest route from your labelled diagram. (c) Find the shortest route from A to J via E and state its length.

Solution

Djikstra\'s Algorithm

1) Set the distance equal to zero for initial node and infinite for all the remainder node, in our problem A is starting node hence the value of A node = 0

2) Mark the initial node i.e. A as current node and other node as unvisited

3) consider the nearest neigbhours and assign the least value as the distance between the nodes

4) Repeat the steps until all the nodes are marked visited

a) For the first part, the shortest route will be equal to

A->B->F->D->G->H->J

Hence the length of the shortest route will be equal to

=> 5 + 2 + 2 + 5 + 1 + 7

=> 22

b) The shortest route will be calculated using the above algorithm starting with the initial node, and then modify the distance of each node by marking the neigbhours visited

If all the neigbhours are visited, then the modifications of the distance have been completed

c) For the C-part, there are two possible solution with the same length paths by moving from A to J via E

The paths are given below

Path 1: A->C->E->G->H->J

Path 2: A->B->F->D->E->G->H->J

minimum distance of both of these paths through E will be equal to 29 units