written 5.7 years ago by
teamques10
★ 68k
|
• modified 5.7 years ago |
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.
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:
and 3 others joined a min ago.
