Step 1: Represent the graph in form of matrix.

Find minimum value of each column and subtract the column minimum value from corresponding column.

Minimum value in column 1, column 2, column 3 and column 4 is 0, 0, 1 and 5. So total minimum value is 6.

After subtracting the Matrix becomes.

$M = \begin{bmatrix} \ ∞ & 0 & 4 & 5 \\ \ 0 & ∞ & 3 & 0 \\ \ 0 & 7 & ∞ & 1 \\ \ 0 & 0 & 0 & ∞ \\ \end{bmatrix}$

Step 4 : Full reduction.

The total reduced cost is = cost (row reduction M) + cost(Column reduction M) = 29 + 6 = 35

$Thus \begin{bmatrix} \ ∞ & 10 & 15 & 20 \\ \ 5 & ∞ & 9 & 10 \\ \ 6 & 13 & ∞ & 12 \\ \ 8 & 8 & 9 & ∞ \\ \end{bmatrix} \ \ \ \text{full reduced matrix} \ \ → \ \ \begin{bmatrix} \ ∞ & 0 & 4 & 5 \\ \ 0 & ∞ & 3 & 0 \\ \ 0 & 7 & ∞ & 1 \\ \ 0 & 0 & 0 & ∞ \\ \end{bmatrix}$

Now as cost of node 2 is optimum, we will set node 2 as E-node and generate its children nodes 5 and 6. Consider path 1, 2, 3 for node 5. Set 1st row and 2nd row to ∞, set 3rd column and 2nd column to ∞. Also M 2 = ∞, M 3 = ∞

$M = \begin{bmatrix} \ ∞ & ∞ & ∞ & ∞ \\ \ ∞ & ∞ & ∞ & ∞ \\ \ ∞ & ∞ & ∞ & 1\\ \ 0 & ∞ & ∞ & ∞ \\ \end{bmatrix}$

Therefore cost of node 5 is optimum cost + reduced cost + old value of M 2 = 35 + 1 + 3 = 39