notes.html

problem 83 · 30 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem asks for the minimum-cost path from the top-left to the bottom-right of an N-by-N grid, where movement is permitted in all four directions - up, down, left, and right. The cost of a path is the sum of the values of the cells it visits, including the starting cell. The crucial observation is that allowing all four directions turns this into a genuine <a class="reference-source" href="https://en.wikipedia.org/wiki/Shortest_path_problem" rel="noopener noreferrer" target="_blank">shortest-path problem</a> on a weighted graph, rather than a grid-restricted DP variant. I model each cell as a node and place a directed edge from every cell to each of its four neighbours, with the edge weight equal to the value of the destination cell. The goal is then the cheapest route from node (0,0) to node (N-1, N-1).
</p>
<p>
Why does this distinction matter? In the right- and down-only variants (Problems 81 and 82), the grid forms a <a class="reference-source" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noopener noreferrer" target="_blank">directed acyclic graph (DAG)</a> - it has no cycles, so I can solve it with <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> in a single fixed-order pass. The moment upward and leftward moves are allowed, cycles become possible and there is no longer a valid evaluation order for a one-pass DP. I need a general shortest-path algorithm. Because every cell value is positive - so every edge weight is non-negative - <a class="reference-source" href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="noopener noreferrer" target="_blank">Dijkstra's algorithm</a> applies and yields an exact answer. Dijkstra maintains a tentative shortest distance to each node, repeatedly finalises the closest unfinalised node, and "relaxes" (improves) the distances of its neighbours. With V = N^2 nodes and a linear scan to find the next node to finalise, the cost is O(V^2) = O(N^4). For N = 80 that is about 40 million comparisons - comfortably fast.
</p>
<h3>Solution Approach</h3>
<h4>Dijkstra's Algorithm with Linear Minimum Scan (C and Python)</h4>
<p>
Both files implement the same algorithm - <a class="reference-source" href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="noopener noreferrer" target="_blank">Dijkstra's algorithm</a> with a linear scan to choose the next node to finalise - so I describe them together and flag language differences as they arise.
</p>
<p>
<strong>Step 1 - Parse the matrix.</strong> In Python I build a list of lists with a comprehension, splitting each non-empty line on commas: <code>[[int(n) for n in line.split(",")] for line in content.splitlines() if line]</code>. In C I scan the raw buffer character by character, using <code>atoi</code> to read each integer and advancing a pointer past spaces, commas, and line breaks. The C parser is more verbose but avoids any intermediate allocation, writing directly into a fixed <code>int matrix[80][80]</code>.
</p>
<p>
<strong>Step 2 - Initialise distances.</strong> Every node's tentative distance starts at a sentinel I call "infinity", computed as the sum of all cell values plus one. This is guaranteed to exceed any real path cost, because no minimal path visits any cell more than once, so the cost cannot exceed the sum of all cells. The start node (0,0) is initialised to its own cell value, since the starting cell's weight is part of the total.
</p>
<p>
<strong>Step 3 - The main loop.</strong> While the target has not been finalised, I scan all unvisited nodes for the one with the smallest tentative distance, mark it visited, and relax its four neighbours: if <code>dist[current] + value(neighbor)</code> improves the neighbour's recorded distance, I update it. Crucially, I stop the instant the target is finalised. <a class="reference-source" href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="noopener noreferrer" target="_blank">Dijkstra's algorithm</a> finalises nodes in non-decreasing distance order, so once the target is extracted its distance is provably optimal and no further work is needed.
</p>
<p>
<strong>Why a linear scan rather than a priority queue?</strong> With V = 6400 nodes, the O(V^2) scan is about 40 million operations - fast enough that the constant-factor and code-complexity cost of a <a class="reference-source" href="https://en.wikipedia.org/wiki/Binary_heap" rel="noopener noreferrer" target="_blank">binary heap</a> is not justified. A heap would give O((V+E) log V), worthwhile for much larger or sparser graphs, but here simplicity wins.
</p>
<p>
<strong>Language-specific differences.</strong> The Python solution keys its <code>distances</code> dictionary and <code>unvisited</code> set on <code>(row, col)</code> tuples and finds the minimum with <code>min(unvisited, key=lambda node: distances[node])</code>. The C solution flattens each node to a single integer index <code>i = row * size + col</code> and stores <code>dist[]</code> and <code>visited[]</code> as contiguous one-dimensional arrays. This flat layout is far more cache-friendly and avoids hash-table overhead, which is the chief reason C runs in 0.0228 s on the full matrix while Python takes 1.5129 s. Both produce the correct answer of 425185.
</p>
</article>