I understand that in some shortest path algorithms on general node weighted graphs, negative cycles lead to nontermination, but here I do not see any problem, so why does the question state that the weights are not negative?
What's the relevance of the numbers not being negative?

Short: because it doesn't matter if there are negative numbers.
Long: Suppose there are negative numbers in the
grid
, if you find the minimum of the whole grid, it must be negative, let's call thismin
. If you take thegrid
and addmin
to each cell: you get agrid'
which doesn't have negative numbers anymore. The minimums have been replaced bymin + min = 0
, everything else is positive. The minimalpath'
you find ingrid'
will have an equivalent (same steps) minimalpath
ingrid
as well andcost(path) = cost(path') + min*len(path)
.

The "because" made me lol :)
Good analysis. Subpaths are of course also equally affected, meaning if path A to a certain cell was originally better than path B to that cell, then path A will still be better than path B after adding
min
everywhere. So solutions will make the same decisions and will find the same optimal path with or without the adding (unless they do something weird :)I suspect the author didn't really make the restriction on purpose.