What's the relevance of the numbers not being negative?


  • 1
    T

    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?


  • 0
    T

    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.).


  • 0

    There are no cycles, though, since edges only go down or right.


  • 0
    T

    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.


  • 1
    T

    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 path in grid as well and cost(path) = cost(path') + min*len(path).


  • 0
    T

    Since you debunked this one, rightfully, I had an idea this morning when I woke up, see new answer.


  • 0

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.