Path Sum: Two Ways

First things first, we'll read in the matrix.

with open("txt/0081_matrix.txt") as f:
    mat = matrix((int(n) for n in line.split(',')) for line in f)

This problem is fundamentally a shortest path problem, a well-studied problem with lots of algorithms to choose from. We'll employ a variant of Dijkstra's algorithm - we would need a different algorithm if the matrix had negative entries.

In short, this algorithm starts with the top-left entry of the matrix and adds its neighbors below and right of it to a search queue. The queue emits entries in the order of smallest path sum from the top-left entry, so the first time we visit an entry, we know the path taken to it is its minimal path. This means when we visit the bottom-right entry, we'll have computed its minimal path and can exit. We also keep track of nodes we've already visited so we don't waste time re-visiting them.

Note that we could improve this even further by implementing a Fibonacci heap for our priority queue, but using a binary heap - built-in to Python! - is plenty fast for this problem.

import heapq

def minimal_path_sum(mat):
    m, n = mat.dimensions()
    
    visited = set()
    queue = [(0, (0, 0))]
    while queue != []:
        cost, (i, j) = heapq.heappop(queue)
        
        if (i, j) in visited:
            continue
        visited.add((i, j))
        
        cost += mat[i, j]
        
        if (i, j) == (m - 1, n - 1):
            break
        
        if i + 1 < m:
            heapq.heappush(queue, (cost, (i + 1, j)))
            
        if j + 1 < n:
            heapq.heappush(queue, (cost, (i, j + 1)))
            
    return cost

minimal_path_sum(mat)

427337

Copyright (C) 2025 filifa

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.