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