Project Euler Problem 83 Statement

In the matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297. $$ \begin{pmatrix} \color{darkred}{131} & 673 & \color{darkred}{234} & \color{darkred}{103} & \color{darkred}{18}\\ \color{darkred}{201} & \color{darkred}{96} & \color{darkred}{342} & 965 & \color{darkred}{150}\\ 630 & 803 & 746 & \color{darkred}{422} & \color{darkred}{111}\\ 537 & 699 & 497 & \color{darkred}{121} & 956\\ 805 & 732 & 524 & \color{darkred}{37} & \color{darkred}{331} \end{pmatrix} $$

Find the minimum path sum in given matrix.

Solution

I'll break down how this Dijkstra's algorithm implementation works for finding the shortest path in a matrix.

Step-by-step analysis

1. Initial Setup:

   M = [
       [1 4 5],
       [2 8 3],
       [3 6 2]
   ]
   dist = [[float('inf')] * n for _ in range(n)]    # Creates distance matrix filled with infinity
   dist[0][0] = M[0][0]                             # Sets starting point distance to its value (1)
   heap = [(M[0][0], 0, 0)]                         # Priority queue: (distance, x, y)

2. Main Loop:

   while heap:
       d, x, y = heappop(heap)      # Gets smallest distance node from heap

   • The heap always gives us the unprocessed cell with smallest current distance
   • Initially, it has (1, 0, 0) - distance 1 at position (0,0)
3. Neighbor Processing:

   for nx, ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:    # Check all 4 directions
       if 0 <= nx < n and 0 <= ny < n:                    # Stay within matrix bounds

   • For each position, checks up, down, left, right neighbors
   • The bounds check ensures we don't go outside the matrix
4. Distance Updates:

   nd = d + M[nx][ny]                   # Calculate new distance
   if nd < dist[nx][ny]:                # If new distance is better
       dist[nx][ny] = nd                # Update distance
       heappush(heap, (nd, nx, ny))     # Add to heap for processing

Let's trace the first few steps of our example:
Starting at (0,0) with value 1:

1. First pop: (1, 0, 0)

   Checks neighbors:
   	Right: (0,1) = 1 + 4 = 5
   	Down: (1,0) = 1 + 2 = 3
   Heap becomes: [(3, 1, 0), (5, 0, 1)]

2. Second pop: (3, 1, 0)

   Checks neighbors:
   	Up: already processed
   	Right: (1,1) = 3 + 8 = 11
   	Down: (2,0) = 3 + 3 = 6
   Heap becomes: [(5, 0, 1), (6, 2, 0), (11, 1, 1)]
   And so on...

The algorithm continues until it either reaches the bottom-right corner or processes all reachable cells. Its key advantages lie in its efficiency: it always processes the shortest current path first using a heap, ensures only potentially optimal paths are updated and processed, and automatically determines the best route through the matrix without redundant calculations.

The final answer dist[n-1][n-1] gives the shortest possible path sum from top-left to bottom-right.

The algorithm has a time complexity of $O(N^2 \log{N})$, where $N$ is the matrix size, as each cell may be processed multiple times due to heap operations. It is efficient and elegant, leveraging a heap for minimum distance selection, combining distance tracking with pathfinding, and focusing solely on minimum distances rather than explicit path tracking, with concise neighbor checking via a directional list.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 83

HackerRank Project Euler 83 the matrix size is increased to 700 × 700.

Last Word