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

Subject: Analysis Of Algorithm

Topic: Dynamic Programming

Difficulty: High

enter image description here

aoa(14) • 863 views
ADD COMMENTlink
modified 21 months ago by gravatar for awari.swati831 awari.swati831250 written 3.3 years ago by gravatar for satishmanje93 satishmanje9320
0

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 COMMENTlink
written 3.3 years ago by gravatar for satishmanje93 satishmanje9320
Please log in to add an answer.