Find a minimum cost path from 1 to 9 in a given graph using dynamic programming.

80views

written 7.8 years ago by

We will assume that the source vertex is 1 and it will have distance 0. Initialize all distance as infinite, except the distance to source itself.

Step 1:

K	1	2	3	4	5	6	7	8	9
1	0	5	2	∞	∞	∞	∞	∞	∞

Step 2:

K	1	2	3	4	5	6	7	8	9
1	0	5	2	∞	∞	∞	∞	∞	∞
2	0	5	2	8	6	8	∞	∞	∞

Step 3:-

Step 4:

Hence the minimum cost path from 1 – 9 is 12.

ADD COMMENT EDIT