DP の履歴(No.7)

Dynamic Programming by Excel without using a VBA macro.†

Finding out the minimal path from the start node to the goal node in a graph with labeled directed arcs.
Fig. 1.
The sheet... dp-1.xlsx

Node IDs. Each node ID is represented by a number. The start node ID should be 1. Node IDs should be sorted.
- Each line represent one node.
Previous nodes for each node. The maximum number of previous nodes should be 4.
Arc values from the previous nodes*. 1000 (represents infinite) is assigned when there is no corresponding arc.

The cell A13 represents a node ID. The ID is one. So this node is the start node.
The cell A19 represents the node, the ID of which is 7. Previous nodes of this node (7) are 4 and 5. They are shown by the cell B19 and C19. The arc value from the node 4 to this node(7) is 10, which is shown by the cell F19. The arc value from the node 5 to this node is 4, which is shown by the cell G19.

=IF(B13<>0,VLOOKUP(B13,$A$13:$N$21,14)+F13,1000)

Calculate the sum of, the arc value (this value) between this node and the previous node, and the value of the previous node which shows the minimal value from the start node to the previous node.
Copy this expression to the area of J13:M21.

=IF(A13=1,0,MIN(J13:M13))

=IF(N13=0,0,MATCH(N13,J13:M13))

Find out the previous arc which minimize the value. It is the selected arc. The arc is identified by the place between J*:M*. When the arc is in the column of J*, it is the 1st arc. When the arc is in the column M*, it is the 4th arc.
Copy this expression to the area of O13:O21

=IF(O13=0,0,INDEX(B13:E13,1,O13))

Find out the previous node (selected node) which minimizes the total value from the start node to this node.
Copy this expression to the area of P13:P21

=IF(P13=0,"",IF(P13=1,"1-"&TEXT(A13,"#####"),VLOOKUP(P13,$A$13:$Q$21,17)&"-"&TEXT(A13,"#####")))

Counter: 3295, today: 3, yesterday: 2