Problem 83: Path Sum: Four Ways

Mathematical Foundation

We model the problem as a shortest-path problem on a weighted directed graph.

Definition. Let $G = (V, E, w)$ be the grid graph where:

• $V = \{(i,j) : 0 \leq i,j \leq n-1\}$, so $|V| = n^2$.
• $E = \{((i_1,j_1),(i_2,j_2)) : |i_1-i_2| + |j_1-j_2| = 1\}$ (4-connectivity), so $|E| = O(n^2)$.
• $w((i_1,j_1) \to (i_2,j_2)) = M[i_2][j_2]$ (cost of entering the destination cell).

The total path cost from $(0,0)$ to $(n-1,n-1)$ is $M[0][0]$ plus the sum of edge weights along the path.

Lemma 1 (Failure of DP). There is no topological ordering of $V$ that is consistent with all possible optimal paths. Proof. In Problems 81 and 82, the restriction to right/down (or right/up/down) moves induces a partial order on cells: $(i,j) \prec (i',j')$ if an edge goes from $(i,j)$ to $(i',j')$, and this partial order is acyclic, enabling DP. With all four directions, the graph contains cycles (e.g., $(0,0) \to (0,1) \to (1,1) \to (1,0) \to (0,0)$), so no topological ordering exists and standard DP is inapplicable. $\square$

Theorem 1 (Dijkstra’s correctness for non-negative weights). Let $G = (V, E, w)$ be a directed graph with $w(e) \geq 0$ for all $e \in E$. Dijkstra’s algorithm correctly computes single-source shortest paths. Proof. We prove the following invariant: when a vertex $v$ is extracted from the priority queue, $\mathrm{dist}[v]$ equals the true shortest-path distance $\delta(s, v)$.

Suppose for contradiction that $v$ is the first vertex extracted with $\mathrm{dist}[v] > \delta(s, v)$. Let $P$ be a true shortest path from $s$ to $v$, and let $(x, y)$ be the first edge on $P$ where $y$ has not yet been extracted. Then $x$ was extracted before $v$ and (by the choice of $v$) $\mathrm{dist}[x] = \delta(s, x)$. When $x$ was extracted, the edge $(x, y)$ was relaxed, so $\mathrm{dist}[y] \leq \delta(s, x) + w(x, y) = \delta(s, y)$. Since $y$ lies on the shortest path to $v$ and weights are non-negative, $\delta(s, y) \leq \delta(s, v) < \mathrm{dist}[v]$. Thus $\mathrm{dist}[y] \leq \delta(s, y) \leq \delta(s, v) < \mathrm{dist}[v]$, meaning $y$ should have been extracted before $v$, a contradiction. $\square$

Corollary 1. Since all matrix entries are positive integers, $w(e) > 0$ for all edges, so Dijkstra’s algorithm correctly solves the grid shortest-path problem.

Editorial

Allowing all four directions destroys the acyclic structure that made dynamic programming work in the previous path-sum problems. Once left moves are allowed, the grid contains cycles, so the natural model is no longer a DP table but a shortest-path graph where each cell is a vertex and moving into a neighboring cell costs that neighbor’s value.

Dijkstra’s algorithm is exactly suited to this setting because all edge weights are positive. At any moment it expands the unsettled cell with the smallest known distance, and from there it generates candidate improvements for the four neighboring cells. Any move that goes outside the grid is discarded, and any move that does not improve the best known distance is ignored. When the bottom-right cell is extracted, its value is the true minimum path sum.

Pseudocode

Create a distance table filled with infinity.
Set the starting cell distance to its own matrix value.
Place the starting cell into a min-priority queue.

While the queue is not empty:
    Remove the cell with the smallest tentative distance

    If this entry is stale, skip it
    If this cell is the bottom-right corner, return its distance

    For each of the four neighboring cells:
        If the neighbor lies outside the grid, ignore it

        Compute the distance obtained by entering that neighbor
        If this improves the recorded distance:
            update the distance table
            insert the improved state into the priority queue

Return the recorded distance for the bottom-right corner.

Complexity Analysis

Time: $O(n^2 \log n)$. The graph has $|V| = n^2$ vertices and $|E| = O(n^2)$ edges. With a binary heap, each of the $O(n^2)$ extract-min operations costs $O(\log n^2) = O(\log n)$, and each of the $O(n^2)$ decrease-key (or insert) operations also costs $O(\log n)$. Total: $O(n^2 \log n)$.

Space: $O(n^2)$ for the distance array and the priority queue.

Remark. Using a Fibonacci heap would give $O(n^2 + n^2 \log n) = O(n^2 \log n)$ anyway. Since the edge weights are bounded integers, a bucket queue or dial’s algorithm could achieve $O(n^2 + n \cdot W)$ where $W$ is the maximum weight.

Answer

#include <bits/stdc++.h>
using namespace std;

int main(){
    // Problem 83: Path Sum Four Ways
    // Dijkstra's algorithm on a grid, moving in all 4 directions.

    int n = 80;
    vector<vector<long long>> M(n, vector<long long>(n));

    ifstream fin("p083_matrix.txt");
    if(fin.is_open()){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                fin >> M[i][j];
                char ch;
                if(j < n-1) fin >> ch;
            }
        }
        fin.close();
    } else {
        n = 5;
        M = {
            {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}
        };
        // Expected for 5x5: 2297
    }

    const long long INF = 1e18;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    // min-heap: (distance, row, col)
    priority_queue<tuple<long long,int,int>,
                   vector<tuple<long long,int,int>>,
                   greater<>> pq;

    dist[0][0] = M[0][0];
    pq.push({M[0][0], 0, 0});

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    while(!pq.empty()){
        auto [d, x, y] = pq.top(); pq.pop();
        if(d > dist[x][y]) continue;
        if(x == n-1 && y == n-1){
            cout << d << endl;
            return 0;
        }
        for(int k = 0; k < 4; k++){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            long long nd = d + M[nx][ny];
            if(nd < dist[nx][ny]){
                dist[nx][ny] = nd;
                pq.push({nd, nx, ny});
            }
        }
    }

    cout << dist[n-1][n-1] << endl;
    // Full 80x80 answer: 425185

    return 0;
}

"""
Problem 83: Path Sum: Four Ways

Find the minimal path sum from top-left to bottom-right of an 80x80 matrix,
moving in all four directions (up, down, left, right).
Uses Dijkstra's algorithm.

Answer: 425185
"""

import os
import heapq

def solve(matrix):
    """Dijkstra's algorithm on the grid."""
    n = len(matrix)
    INF = float('inf')
    dist = [[INF]*n for _ in range(n)]
    dist[0][0] = matrix[0][0]
    pq = [(matrix[0][0], 0, 0)]

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while pq:
        d, x, y = heapq.heappop(pq)
        if d > dist[x][y]:
            continue
        if x == n-1 and y == n-1:
            return d
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                nd = d + matrix[nx][ny]
                if nd < dist[nx][ny]:
                    dist[nx][ny] = nd
                    heapq.heappush(pq, (nd, nx, ny))

    return dist[n-1][n-1]

def read_matrix(filename):
    matrix = []
    with open(filename) as f:
        for line in f:
            row = list(map(int, line.strip().split(',')))
            matrix.append(row)
    return matrix

def main():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    filepath = os.path.join(script_dir, "p083_matrix.txt")

    if os.path.exists(filepath):
        matrix = read_matrix(filepath)
    else:
        matrix = [
            [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],
        ]
        # Expected: 2297

    answer = solve(matrix)
    print(answer)
    # Full 80x80 answer: 425185