Path Sum: Two Ways

In the $5$ by $5$ matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to $2427$.

$$
\begin{pmatrix}
\color{red}{131} & 673 & 234 & 103 & 18\\
\color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\
630 & 803 & \color{red}{746} & \color{red}{422} & 111\\
537 & 699 & 497 & \color{red}{121} & 956\\
805 & 732 & 524 & \color{red}{37} & \color{red}{331}
\end{pmatrix}
$$

Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing an $80$ by $80$ matrix.

This problem belongs to the class of problems known as the Shortest Path Problem, solved by a method called Dynamic Programming. We’ll use a variation of Dijkstra’s algorithm with small modifications due to the constraint of only being able to move right and down in the X by X matrix.

Unfortunately, I can’t directly open or work with files. However, I can actually demonstrate you a Python solution for the problem, using a 5 by 5 matrix as an example.

Let me explain how we might do this:

1. Import the libraries
“`
import numpy as np
“`
2. Define a function to find the minimal path:
“`python
def find_minimal_path(matrix):
# We’ll first get the size of the matrix
size = len(matrix)

# Then, we’ll create a “cost matrix”, filling it with infinity
cost_matrix = np.full((size, size), np.inf)

# We’ll start in matrix[0][0]. That’s why cost_matrix[0][0] is matrix[0][0]
cost_matrix[0][0] = matrix[0][0]

# We are going to save the operations that we have to check in “next_operations”
next_operations = [(0, 0)]

# delta allows us to check the down and right positions
delta = [(1, 0), (0, 1)]

# While we have operations to check
while next_operations:
x, y = next_operations.pop(0)
for dx, dy in delta:
nx, ny = x + dx, y + dy
if nx < size and ny < size: cost = matrix[nx][ny] + cost_matrix[x][y] if cost < cost_matrix[nx][ny]: cost_matrix[nx][ny] = cost next_operations.append((nx, ny)) return cost_matrix[-1][-1] ``` 3. Now, given a $5x5$ matrix ```python matrix5x5 = [ [131, 673, 234, 103, 18], [201, 96, 342, 965, 150], [630, 803,746, 422, 111], [537, 699, 497, 121, 956], [805, 732, 524, 37, 331] ] ``` we could call our function ```python print(find_minimal_path(matrix5x5)) ``` to get the minimal path sum - $2427$. 4. For your particular case, you should read the matrix from the file, which in Python might look something like this: ```python matrix80x80 = np.loadtxt('matrix.txt', delimiter=',').tolist() print(find_minimal_path(matrix80x80)) ``` Remember to replace 'matrix.txt' with your actual filepath and ensure your file contains a comma separated 80X80 matrix of integers. Run the Python script and you should get your desired minimum path sum. Also, keep in mind that this process, being brute force, could be very computational heavy due to the size of your matrix.

More Answers: