Solution

Answer: 425185

Treat the matrix as a weighted graph:

Each cell is a vertex.
From each cell, you may move up, down, left, or right.
Entering a cell adds that cell’s value to the total path cost.

We want the minimum-cost path from the top-left corner to the bottom-right corner.

Because all weights are positive, this is a classic application of Dijkstra’s shortest-path algorithm.

Mathematical analysis

Let the matrix be $A$ of size $n \times n$.

Define:

$$d(i,j)$$

to be the minimal path sum needed to reach cell $(i,j)$.

Unlike Problem 81, we are allowed to move in four directions, so there is no simple dynamic programming recurrence such as

$$d(i,j)=A_{i,j}+\min(d(i-1,j),d(i,j-1)).$$

Why? Because allowing movement upward and left creates cycles.

So instead we model the matrix as a graph.

Graph formulation

Each cell $(i,j)$ is a node.

Edges exist between orthogonally adjacent cells:

$$(i,j)\leftrightarrow(i+1,j),\quad (i,j)\leftrightarrow(i-1,j),\quad (i,j)\leftrightarrow(i,j+1),\quad (i,j)\leftrightarrow(i,j-1)$$

when those coordinates are inside the matrix.

The cost of moving into a neighboring cell equals the value of that neighboring cell.

If the starting cell is $(0,0)$, then the initial distance is

$$d(0,0)=A_{0,0}.$$

All edge weights are positive, so Dijkstra’s algorithm guarantees the optimal shortest path.

Dijkstra’s algorithm

Maintain:

a priority queue ordered by current best distance,
a distance table initialized to infinity.

At each step:

Extract the node with smallest tentative distance.
Relax all neighbors:

$$\text{newdist} = d(u) + A(v)$$ 3. If the new distance is smaller, update it and push into the heap.

When the destination node is removed from the heap, we have the optimal answer.

The complexity is

$$O(V\log V + E\log V).$$

For an $80\times80$ matrix:

$$V = 6400,\qquad E \approx 4V,$$

which is extremely manageable.

Python implementation

import heapq

# Read matrix from file
with open("0083_matrix.txt") as f:
    matrix = [list(map(int, line.strip().split(",")))
              for line in f]

n = len(matrix)

# Distance table
INF = float('inf')
dist = [[INF] * n for _ in range(n)]

# Starting point
dist[0][0] = matrix[0][0]

# Priority queue: (distance, row, col)
pq = [(matrix[0][0], 0, 0)]

# Possible movements
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while pq:
    d, r, c = heapq.heappop(pq)

    # Ignore outdated entries
    if d != dist[r][c]:
        continue

    # Reached destination
    if (r, c) == (n - 1, n - 1):
        print(d)
        break

    # Relax neighbors
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc

        if 0 <= nr < n and 0 <= nc < n:
            nd = d + matrix[nr][nc]

            if nd < dist[nr][nc]:
                dist[nr][nc] = nd
                heapq.heappush(pq, (nd, nr, nc))

Code walkthrough

Reading the matrix

matrix = [list(map(int, line.strip().split(",")))
          for line in f]

Each line in the file contains comma-separated integers.

Distance initialization

dist = [[INF] * n for _ in range(n)]
dist[0][0] = matrix[0][0]

Initially every node is unreachable except the start.

Priority queue

pq = [(matrix[0][0], 0, 0)]

The heap stores:

$$(\text{current distance}, \text{row}, \text{column})$$

so the smallest-distance node is processed first.

Main Dijkstra loop

d, r, c = heapq.heappop(pq)

Take the node with smallest tentative distance.

Ignore stale heap entries

if d != dist[r][c]:
    continue

A better path may already have been discovered.

Neighbor relaxation

nd = d + matrix[nr][nc]

Moving into a neighbor adds that neighbor’s cell value.

If this path improves the known best distance:

if nd < dist[nr][nc]:
    dist[nr][nc] = nd

update and push into the heap.

Verification on the $5\times5$ example

Running the algorithm on the sample matrix produces:

$$2297$$

which matches the problem statement exactly.

Final verification

The algorithm is mathematically correct because all edge weights are positive and Dijkstra’s algorithm finds shortest paths in such graphs.
The matrix has only $6400$ nodes, so runtime is small.
The known Project Euler result for Problem 83 is:

Answer: 425185

Project Euler Problem 83