The Dynamic Programming Labelling Procedure

• Print

Labelling dynamic programming networks is a real problem. There are many different notations, starting from the left hand side of a diagram or the right hand side, using coordinate (x,y) notation, or just numbering the states. I will explain the coordinate notation starting from the right.

This notation takes the form (x,y) with

x equal to the maximum number of arcs that must be traversed in any path towards the terminal node

y equal to the order of the node as we go down the diagram vertically.

To demonstrate I will label the nodes (states) for the problem below.

H is given the label (0,1).

F is given the label (1,1) and G is given the label (1,2), because the longest path from G to H is GFH (two arcs).

D is given the label (1,3) because the longest path from D to H is DGFH (three arcs) and E is given the label (3,2) because the longest path from E to H is EGFH (three arcs).

B is given the label (5,1) since the longest path from B to H is BEDGFH (five arcs).

C is given the label (5,2) since the longest path fom C to H is CEDGFH (five arcs).

A is given the label (6,1) since the longest label from A to H is ACEDGFH (six arcs).