Recently I came across a problem (https://algs4.cs.princeton.edu/44sp/ question #34). I've already devised an algorithm that modifies Dijkstra's algorithm under the assumption that the graph only has positive weights. I was wondering, how would I go about modifying Bellman-Ford (or some other negative weight shortest path algorithm) to solve this problem in $$$O(n^2m)$$$ time?
Note: I also saw something similar in CLRS (bitonic shortest paths), but the solution found here: https://walkccc.me/CLRS/Chap24/Problems/24-6/ is a extremely difficult to understand.
I had an idea about relaxing the edges in increasing order. I've implemented this, however, I'm having a hard time proving why this is correct. Any ideas on why this would work? (Given we have no negative cycles)