![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[ExcelEx]] * Dynamic Programming by Excel without using VBA macro. [#k8ac001e] - Finding out the minimal path from the graph - &ref(DP/dp-1-img.jpg,50%); - The sheet... &ref(DP/dp-1.xlsx); ** Input [#f6744253] - Node numbers. The start node should be 1. Nodes numbers should be sorted. - Previous node numbers for each node number. The muximum previous nodes number should be 4. - Arc values from the previous nodes to each node. All values, include arc values and intermediate values, should be less than 1000. ** Output [#g3e710b2] - The minimal value from the start node to the goal node. - The minimal path from the start node to the goal node. ** Key excpressions [#s5d8268b] *** J13 [#xe0335cd] =IF(B13<>0,VLOOKUP(B13,$A$13:$N$21,14)+F13,1000) - Calculate the arc value between this node and the previous node, plus the value (minimal value from the start node from the node) of the previous node. - Copy this expression to all of this column. *** N13 [#d744f0cc] =IF(A13=1,0,MIN(J13:M13)) - Find out the minimal value from the previous nodes to this node. - Copy this expression to all of this column. *** O13 [#hd19795a] =IF(N13=0,0,MATCH(N13,J13:M13)) - Find out the previous arc index which minimize the value. - Copy this expression to all of this column. *** P13 [#k0befaa9] =IF(O13=0,0,INDEX(B13:E13,1,O13)) - Find out the previous node which minimize the value. - Copy this expression to all of this column. *** Q13 [#d88ce4e1] =IF(P13=0,"",IF(P13=1,"1-"&TEXT(A13,"#####"),VLOOKUP(P13,$A$13:$Q$21,17)&"-"&TEXT(A13,"#####"))) - Construct the minimal path from the start node to this node. - Copy this expression to all of this column. ---- #counter
