Example: Minimum Cost Path - rFronteddu/general_wiki GitHub Wiki

Given a matrix costs, you want to go from top left to bottom right following the less expensive path. Note that you can only move right and down

Cost matrix

1	3	5	8
4	2	1	7
4	3	2	3

The idea is to first compute the costs for the first row and the first column, then proceed row by row picking the min between the top and the left col.

1	4	9	17
5	6	7	14
9	9	9	12

minPath(x)
    n = x.len - 1
    m = x[0].len - 1
    let d[0..n, 0..m] be a table

    d[0,0] = x[0,0]

    for i = 1 to n
        d[i,0] = d[i-1,0] + x[i,j]

    for j = 1 to m
        d[0,j] = d[j-1,0] + x[i,j]

    for i = 1 to n
        for j = 1 to m
            d[i,j] = x[i,j] + min(d[i-1,j], d[i, j-1])

    print("Min cost: " + d[n,m])

    path = []

    i = n
    j = m
    
    path.add((0,0)) 
    while i > && j > 0
        path.add((i,j))
        if d[i-1,j] < d[i,j-1]
            i--
        else 
            j--

    // add remaining path
    while i > 0
        path.add((i,j))

    while j > 0
        path.add((i,j))


    print("Path: ")
    for cell in path
        print("[" + cell[0] + "]\n")