Minimum cost path of matrix using Python

Question

I was reading this article about finding the minimum cost path from (0,0) to any (m,n) point in a matrix. Using python the author has provided 2 solutions in Python.

The first one solves it by using a backward induction technique through recursion while the second one uses an auxiliary table (tc). I was wondering if I could solve it using forward induction and without the need of an additional table. Here's my solution:

def test(target_matrix, cost, i, j, m, n):
    if i == m and j == n:
        return cost
    if i + 1 > m:
        cost += target_matrix[i][j + 1]
        return test(target_matrix, cost, i, j + 1, m, n)
    if j + 1 > n:
        cost += target_matrix[i + 1][j]
        return test(target_matrix, cost, i + 1, j, m, n)
    if i + 1 <= m and j + 1 <= n:
        ret_cost, i, j = min(target_matrix[i + 1][j], target_matrix[i][j + 1], target_matrix[i + 1][j + 1], i, j)
        cost += ret_cost
        return test(target_matrix, cost, i, j, m, n)


def min(x, y, z, i, j):
    if x < y:
        if x < z:
            return x, i + 1, j
        else:
            return z, i + 1, j + 1
    else:
        if y < z:
            return y, i, j + 1
        else:
            return z, i + 1, j + 1


if __name__ == '__main__':
    input = [
        [11, 9, 3],
        [3, 1, 0],
        [1, 3, 2]
    ]
    res = test(input, input[0][0], 0, 0, 2, 2)
    print(res)

What are your comments on this? What do you think are its drawbacks compared to the two solutions provided in the article? I'm particularly interested in comments regarding the time and space complexity of my algorithm.

Answer 1

You can do it without using any additional table. I want to do it without recursion, but you can create recursive version very easily yourself.

First, let's see what is the second table in the link solution. In that table, the value of each table cell is the minimum cost for accessing that cell. But what about the cost table? in the cost table, the value of each cell is simply the cost of that cell.

So, for turning the cost table to the minimum cost table of each cell, we need to run the minimum-path algorithm on it.

For each cell, we will choose the minimum value of {cost of upper cell + cost of the current cell, cost of top-left cell + cost of the current cell, cost of left cell + cost of current cell}. Don't forget that we only allowed moving to the right, down and right-down, and because now we are moving in the opposite direction in each row, we should consider opposite movements.

Talking is enough, let's code speaks a little:

def test(cost, m, n):
    # Initializing the first column
    for i in range(1, m + 1):
        cost[i][0] += cost[i - 1][0]
    # Initializing the first row
    for j in range(1, n + 1):
        cost[0][j] += cost[0][j - 1]
    for j in range(1, n + 1):
        for i in range(1, m + 1):
            cost[i][j] += min(cost[i - 1][j - 1], cost[i][j - 1], cost[i - 1][j])
    return cost

Two first steps are like the solution in the link. In the first column of the table, we don't have any left cell, so for avoiding complex works on indexes, we first calculate the weight of cells those belong to the first column of the table.

Again, we should do different work for the first row of the table. Because this row has no top and top left cell.

Then, we start to calculate the minimum value for moving to each cell for 1..=m column and 1..=n row. We Don't calculate the weights of cells that are after the desired cell, because it is not necessary.

In the cost table, for calculating the values of each row, we only need the values of the previous row. So, As you can see, we can use the cost table as the minimum-cost paths table without any problem.

Here is the final code:

def trip_min(num1, num2, num3):
    return min([num1, num2, num3])[0]


def test(cost, m, n):
    for i in range(1, m + 1):
        cost[i][0] += cost[i - 1][0]
    for j in range(1, n + 1):
        cost[0][j] += cost[0][j - 1]
    for j in range(1, n + 1):
        for i in range(1, m + 1):
            cost[i][j] += min(cost[i - 1][j - 1], cost[i][j - 1], cost[i - 1][j])
    return cost


if __name__ == '__main__':
    input_list = [[i+j for i in range(10)] for j in range(10)]
    res = test(input_list, 8, 8)
    print(res)
    print(res[8][8])

I changed the trip_min function and used the min function instead of writing the code of minimum by myself. Why? Because using builtin functions is always better than writing your own code, unless those behavior or performance is not exactly what you want. That reduces the probability of bug in your code any many times makes your code faster and cleaner.

Also, I changed the name of the cost table form input to the input_list. input is the name of a build-in function of the Python and it's a very bad idea to declear a variable with the same name of other things. That will make you and your collaborators confused about the code in the future.

You can get the minimum cost to each cell by calling res[row][col] on the result of the test function (You can't do that on the indexes after m and n as described).

The last thing I should say is if you use the cost table as the minimum-cost paths table, you can not re-use that costs. Because we actually changed the value of the input_list. As you may know, if you send a list as a parameter to a function, and you change the values of that list, the original list will change. Why? Because Python will not copy the lists when you pass them as function parameters.

So if you want to calculate minimum paths for different cells, it's better to first calculate the minimum-path table for entire cost table (by passing m and n to the lengths of the table), and then access values from the result table.

And, I promise it's the final note, don't forget that res and input_list both are exactly same lists (Actually, you can remove the return in the test function).