0
4.0kviews
Find a minimum cost path from 3 to 2 in the given graph using dynamic programming.

Find a minimum cost path from 3 to 2 in the given graph using dynamic programming.

enter image description here

1 Answer
0
265views
  1. An edge-weighted graph is a graph where we associate weights or costs with each edge.
  2. A minimum cost path of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.
  3. Problem

enter image description here

Sr.No Step No. executed Edges Considered Edges Selected Cost Spanning Tree
1 1 - - - enter image description here
2 1 (3,4),(3,5) (3,4) 3 enter image description here
3 2 (4,5)(4,2) (4,5) 5 enter image description here
4 3 (5,2) (5,2) 10 enter image description here
5 4 - - - Stop

Hence, from the above table the minimum cost path from node 3 to node 2 is 3452 with minimum cost of 10.

Please log in to add an answer.