I understand that in some shortest path algorithms on general node weighted graphs, negative cycles lead to non-termination, but here I do not see any problem, so why does the question state that the weights are not negative?
I guess it's just simplifies the problem and allows for another class of solutions: ones which would fail on negative cycles.
If you don't know or like dynamic programming you can traverse the solution space as a graph and find the shortest path (Dijkstra, A*, etc.).
Hmm, that's right, then it really doesn't make a difference.
Maybe there's some less-known algorithm where
>=0 can be assumed and incorporated.
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 this
min. If you take the
grid and add
-min to each cell: you get a
grid' which doesn't have negative numbers anymore. The minimums have been replaced by
min + -min = 0, everything else is positive. The minimal
path' you find in
grid' will have an equivalent (same steps) minimal
grid as well and
cost(path) = cost(path') + min*len(path).
Since you debunked this one, rightfully, I had an idea this morning when I woke up, see new answer.
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.