0
3.5kviews
Apply Dijkstras and Bellman Fords algorithm to the given network as shown in fig and find at least the cost path between source node 1 to all other nodes.

enter image description here

1 Answer
0
61views

PART 1: USING DIJKSTRA'S ALGORITHM:

Let node 1 --> A, 2 --> B, 3 --> C, 4 --> D, 5 --> E, 6 --> F.

Step 1: Starting node is A. Enter it into group P as shown in the table a. Add neighbours B, C, F to temporary group T.

Table a:

Permanent (T) Temporary (T)
A B(A,1), C(A,9), F(A,14)

Step 2: Now pick up neighbour with smallest cost i.e, B and add it to group P. As B is added to P group we have to add neighbours C and D to T group as shown in table b.

Table b:

Permanent (T) Temporary (T)
A B(A,1), C(A,9), F(A,14)
A, B(A,1) C(A,9), F(A,14), C(A,11), D(A,16)

Step 3: Now move C from T to P and add neighbour D to group P as shown in table c.

Table c:

Permanent (T) Temporary (T)
A B(A,1), C(A,9), F(A,14)
A, B(A,1) C(A,9), F(A,14), C(A,11), D(A,16)
A, B(A,1), C(A,9) F(A,14), C(A,11), D(A,16), D(C,20), F(C,11)

Step 4: Now continue in the same manner to get final table as shown in table d.

Table d:

Permanent (T) Temporary (T)
A B(A,1), C(A,9), F(A,14)
A, B(A,1) C(A,9), F(A,14), C(A,11), D(A,16)
A, B(A,1), C(A,9) F(A,14), C(A,11), D(A,16), D(C,20), F(C,11)
A, B(A,1), C(A,9), F(C,11) F(A,14), C(A,11), D(A,16), D(C,20), E(F,20)
A, B(A,1), C(A,9), F(C,11) D(A,16) F(A,14), C(A,11), D(C,20), E(F,20), E(D,24)
A, B(A,1), C(A,9), F(C,11) D(A,16) , E(F,20) Null (Stop)

Shortest path from node 1 to all other nodes is as shown in figure below.

enter image description here

PART 2 : USING BELLMAN FORD ALGORITHM:

Let node 1 --> A, 2 --> B, 3 --> C, 4 --> D, 5 --> E, 6 --> F. Distance from node 1 to all other nodes is as shown in table e.

Table e:

Node 1 arc distance 2 arcs distance 3 arcs distance
A 0 0 0
B 1 -- --
C 9 -- --
D infinite 16 ( Due to B) 22 (Due to C)
E infinite 23 (Due to F) 20 (Due to F)
F 14 11 (Due to C) 13 (Due to C)

Shortest path from node 1 to all other nodes using Bellman Ford Algorithm is as shown in the figure below:

enter image description here

Please log in to add an answer.