8 Use Dijkstras Algorithm to find the minimum path from S to

8. Use Dijkstra\'s Algorithm to find the minimum path from S to T of the following graph: R 6 4 w

Solution

As per Dijkstra\'s algorithm, we find all possible paths from S to T and mark their corresponding path weights and then we choose with path is with minimum weight. Let us mark all the paths with their corresponding weights:

SPQRT = (2+5+6+2) = 15

SPQRYWT = 18

SPQXYRT = 27

SPQXYWT = 28

SPQXVWT = 31

SPXQRT = 20

SPXQRYWT = 24

SPXYRT = 19

SPXYWT = 20

SPXVWT = 23

SUVWT = 15

SUVWYRT = 20

SUVXYWT = 28

SUVXRT = 27

SUXVWT = 21

SUXYWT = 18

SUXYRT = 17

SUXQRT = 19

On all other paths, the weight gets more and more..so we can check which amongst these paths has lowest weight.

Therefore, the paths with lowest weights are SPQRT and SUVWT and lowest weight is 15.