Question

Below is a network. Each node or router has a letter from A to P.

The cost of each link is shown in the graph. The cost of each link is in the middle of the link between the two letters. (It is a perfect grid although the links may not align completely)

The cost of some links is shown as the * symbol. The cost of each of those links correspond the first letter of your last name. If your last name starts with A then the cost of all the links that have a * is 1. If your last name starts with B then the cost of all the links that have a * is 2 (and so on). Assume that the cost of the link is the same in both directions. For example, assume that A to B is 15 and B to A is also 15.

   M ----14---- N ---- *----O ----13---- P

   |                     |                |                   |

14                 10               10                 6

   |                     |                  |                  |

   I ---- 14 ---- G ----11----K ---- * ----L

   |                |                 |                |

   8                     15                  5                  18

   |                   |                 |                    |

   E ----11----- F --- * ---- G ---12 -----H

   |                     |                   |                  |

   *                  16               13                *

   |                |               |                 |

   A ----15 ----- B ---12 --- C ---- *---- D

Use the shortest path algorithm to find the shortest path from the following nodes below. For each of the following pairs write the cost of the path followed by the node sequence (example A->B->C)

1. A to   P
2. A to   N

   3.    A to   K

4. O to   A
5. H to   A

Answer 1

Since the first letter of my last name is 'K' hence the cost of all links that contains a * will be 11.

A = 1, B = 2, C = 3,………………. K = 11

Please refer the image below :

Hint: To find the shortest path sooner, always select the link with least cost first and then make combinations.

Always try to make combinations in mind and note down the costs of path using calculators rather than making the table (until and unless making table is necessarily stated) else, it will consume a lot of time.

Shortest path from

1) A – P

Here I first selected the links with least costs such as ((G - K) = 5 and (L - P) =6) and then made combinations around those links.

A – E – F – G – K – L – P

11 + 11 + 11 + 5 + 11 + 6 = 55

2) A – N

A – E – I – M – N

11 + 8 + 14 + 14 = 47

          Or

A – B – F – G – N

11 + 11 + 15 + 10 = 47

A – E – I – G – N = 43 (wrong)

(Not feasible because we have to follow node sequence and here, I is coming before G)

3) A – K

A – B – C – G – K

15 + 12 + 13 + 5 = 45

A – E – I – G – K = 44 (Though shortest distance but wrong)

(Not feasible because we have to follow node sequence and here, I is coming before G)

4) O – A

O – K – G – C – B – A   (Here too follow the reverse node sequencing )

10 + 5 + 13 + 12 + 15 = 55

5) H – A

H – G – F – E – A            (Here too follow the reverse node sequencing )

11 + 11 + 11 + 12 = 45

Rest all other paths are longer than above ones.