0

2.9kviews

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

written 8.4 years ago by teamques10 ★ 68k

•   modified 4.6 years ago

analysis of algorithms

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

0

97views

written 8.4 years ago by teamques10 ★ 68k

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:-

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

Step 4:

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

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

ADD COMMENT SHARE EDIT