“Dynamic programming is an algorithm design method that can
be used when the solution to a problem may be viewed as the result of a
sequence of decisions”
Minimum spanning of multistage graph using dynamic
programming
a. Forward
Approach
b. Backward
Approach
a. Forward
Approach:
Spanning
a multiple stage graph using following considerations
· Identify source and destination nodes.
· Find all possible paths to reach destination from source and sum of weights of adjacent nodes.
· The path giving the least weight will be the minimum spanning path.
Consider
a multistage graph given below

Identifying source and destination
nodes.
Source node > S
Destination node > D
The possible ways to
connect S & D
d(S,D) = min { 1 + d(A,D)
; 2 + d(F,D) ; 5 + d(C,D) } >1
d(A,D) = min{ 4 + d(B,D) ; 11 + d(G,D) }
= min{ 4 + 18 ; 11 + 13 } ‘Substation weights
= min{ 22 ; 23 }
d(A,D) = 22 >2
d(F,D) = min{ 9 + d(B,D) ; 5 + d(G,D) ; 16 + d(E,D) }
= min{ 9 + d(B,D) ; 5 + d(G,D) ; 16 +
d(E,D) }
= min{ 9 + 18 ; 5 + 13 ; 16 + 2} ‘Substation weights
= min{ 27 ; 18 ; 18}
d(F,D) = 18 >3
d(C,D)
= min{ 2 + d(E,D) }
= min{ 2 + 2} ‘Substation weights
= min{ 4}
d(C,D) = 4 >4
Substation of 2,3,4 in 1
gives
d(S,D) = min { 1 + d(A,D) ; 2 + d(F,D) ; 5 + d(C,D) }
d(S,D) = min { 1 + 22 ; 2 + 18 ; 5 + 4 }
d(S,D) = min { 23 ; 20 ; 9 }
d(S,D) = 9
Hence minimum spanning
path from S to D is
S > C > E > D
according to Forward Approach.
b. Backward
Approach:
Backward
Approach is just the reverse of forward
approach, here Source node and the next node is considered at every stage.
Considering
same Multi staged Graph,
1 > 2
Source node S to next
nodes A, F and C
d(S,A) = 1
d(S,F) = 2
d(S,C) = 5
1 > 2 > 3
Source node S to next
nodes B, G and E
d(S,B) = min{ 1 + d(A,B) ;
2 + d(F,B)}
= min{ 1 + 4 ; 2 + 9}
= min{ 5 ; 11}
d(S,B) = 5
d(S,G) = min{ 1 + d(A,G) ;
2 + d(F,G)}
= min{
1 + 11 ; 2 + 5}
= min{ 12 ; 7}
d(S,G) = 7
d(S,E) = min{ 2 + d(F,E) ;
5 + d(C,E)}
= min{
1 + 16 ; 5 + 2}
= min{ 17 ; 7}
d(S,E) = 7
1 > 2 > 3 > 4
d(S,D) = min{ 5 + d(B,D)
; 7 + d(G,D) ; 7 + d(E,D)}
= min{
5 + 18 ; 7 + 13 ; 7 + 2}
= min{ 23 ; 20 ; 9}
d(S,D) = 9
Hence minimum spanning
path from S to D is
S > C > E > D
according to Backward Approach.
Well explanation is good and continue d topic...
ReplyDeleteThank you... good explantion
ReplyDeleteyour made a minor mistake in calculating d(A,T) in forward approach ...ur ans is correct coincidently cz ultimately we get min as 22.
ReplyDeleteSorry, I did made a mistake in calculating the distance for nodes A,D in forward approach. Thanks for stopping here and correcting me.
Delete