Detailed mathematical approach

Problem Summary

We are given an \(80\times80\) matrix \(M\). A path starts at the upper-left cell \((0,0)\), ends at the lower-right cell \((79,79)\), and may move one step up, down, left, or right as long as it stays inside the matrix. The cost of a path is the sum of all visited cell values, so both the starting cell and the ending cell contribute to the total.

The extra freedom to move in all four directions is the essential difference from the earlier path-sum problems. Once left and up moves are allowed, the dependency graph of the cells has cycles, so there is no row-by-row or column-by-column order that makes a one-pass dynamic program valid.

Mathematical Approach

Let \(d(r,c)\) denote the minimum possible path sum for any valid path from \((0,0)\) to \((r,c)\). The implementations solve for this quantity by turning the matrix into a weighted graph and then running Dijkstra's algorithm.

From Matrix to Weighted Grid Graph

Each cell is a vertex. Two vertices are connected when the corresponding cells are orthogonal neighbors in the grid. If a step moves from \((r,c)\) to a neighbor \((r',c')\), the step cost is the value of the destination cell \(M_{r',c'}\). With this convention, a path

$P=((r_0,c_0),(r_1,c_1),\dots,(r_k,c_k))$

has total cost

$\operatorname{cost}(P)=M_{r_0,c_0}+\sum_{t=1}^{k} M_{r_t,c_t}=\sum_{t=0}^{k} M_{r_t,c_t}.$

So the Project Euler question is exactly a shortest-path problem from the start vertex to the target vertex.

All matrix entries are positive, so every directed edge has positive weight. That matters twice. First, any path containing a cycle can be shortened by deleting the cycle, so an optimal path never needs to revisit a cell. Second, positive weights are exactly the hypothesis that makes Dijkstra's greedy extraction rule correct.

The Optimality Equation and Why It Is Not a Simple DP Sweep

The minimum cost function satisfies the relation

$d(0,0)=M_{0,0},$

and for every other cell,

$d(r,c)=M_{r,c}+\min_{(u,v)\in \mathcal{N}(r,c)} d(u,v),$

where \(\mathcal{N}(r,c)\) is the set of in-bounds orthogonal neighbors of \((r,c)\).

This is the right optimal-substructure statement: the last step into \((r,c)\) must come from one of its neighbors. The difficulty is that these equations are coupled. A value such as \(d(r,c)\) may depend on \(d(r,c+1)\), while \(d(r,c+1)\) may also depend on \(d(r,c)\) through a different route. That feedback loop is exactly why Problems 81 and 82 admit simpler dynamic programs but Problem 83 does not.

Dijkstra's Invariant on This Grid

Dijkstra's algorithm keeps a tentative distance for each cell and a min-priority queue of candidate states. Whenever the cell with the smallest tentative value is extracted, that value is final. The relaxation step for a neighbor \((r',c')\) is

$\text{candidate}=d(r,c)+M_{r',c'},$

and we update the neighbor if this candidate is smaller than its current best known value.

The correctness proof is the standard positive-weight argument. Assume that some extracted cell is the first one whose tentative value is larger than the true optimum. Along a truly optimal path to that cell, look at the first cell not yet extracted, and let the previous cell on that path be its predecessor. The predecessor must have been extracted earlier with its correct value, so relaxing the next edge would have inserted a tentative value no larger than the true optimum of the final cell. That contradicts the choice of the supposedly first bad extraction. Therefore every extracted cell is finalized correctly, including the destination.

Worked Example: the 5x5 Checkpoint Matrix

The sample used by the implementation is

$\begin{pmatrix} 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 \end{pmatrix}.$

One optimal route is

$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(0,2)\to(0,3)\to(0,4)\to(1,4)\to(2,4)\to(2,3)\to(3,3)\to(4,3)\to(4,4).$

Its cost is

$131+201+96+342+234+103+18+150+111+422+121+37+331=2297.$

The upward move from \((1,2)\) back to \((0,2)\) is the key feature: the best path is not monotone. That single step already shows why a right-and-down dynamic program is no longer enough.

How the Code Works

The C++, Python, and Java implementations all read the matrix, build a two-dimensional distance table, and initialize every entry to infinity except the start cell. The priority queue is seeded with the start state whose cost is the value of the upper-left cell itself.

They then repeat the same loop: extract the state with minimum tentative cost, ignore it if the queue entry is stale, and otherwise try all four orthogonal neighbors. Whenever moving into a neighbor produces a smaller total, the implementation records the better distance and pushes a fresh queue entry. This is the lazy-heap version of Dijkstra: there is no explicit decrease-key operation, so obsolete entries are simply skipped when they reappear.

The three languages differ only in presentation details. The C++ implementation also checks the standard 5x5 sample and can stop as soon as the target cell is extracted, while the Python and Java implementations continue the same relaxation process until the queue is empty. In every case, the reported answer is the finalized distance of the bottom-right cell.

Complexity Analysis

If the matrix has \(R\) rows and \(C\) columns, then the graph has \(V=RC\) vertices and at most \(E\le 4RC\) directed neighbor relaxations. With a binary heap, Dijkstra runs in

$O(E\log V)=O(RC\log(RC)).$

For an \(n\times n\) grid this is \(O(n^2\log n)\), since \(\log(n^2)=2\log n\).

The distance table uses \(O(RC)\) space, and the priority queue also stays within \(O(RC)\) stored states up to constant-factor duplicates from the lazy updates. For the actual \(80\times80\) instance, this means only \(6400\) vertices and at most \(25600\) neighbor edges, which is easily small enough for an ordinary heap-based shortest-path computation.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=83
2. Dijkstra's algorithm: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
3. Shortest path problem: https://en.wikipedia.org/wiki/Shortest_path_problem
4. Grid graph: https://en.wikipedia.org/wiki/Grid_graph
5. Priority queue: https://en.wikipedia.org/wiki/Priority_queue