Math
The cheapest route
Terrain where a step costs the price of the cell you enter, and the wave of settled vertices spreads by price rather than by distance. One slider drops a negative edge on the map and has three measured regimes: right, wrong, and no shortest path at all.
What happens
A step here costs the price of the cell you walk into, so the wave of settled vertices does not spread in circles: it runs far through a cheap valley and stalls against an expensive ridge. That picture is the whole difference between a breadth-first search and this one. While the weights are non-negative the answer is provably shortest, and it is checked here against Bellman-Ford relaxed to a fixed point - never against a second run of the same algorithm - plus a full enumeration of simple paths on the small grids. On flat terrain the cost has a closed form, w(i + j), because every monotone route costs the same. The counts are identities too: every vertex is closed exactly once and every edge relaxed exactly once, 4m(m−1) of them. Then the discount slider drops a single directed negative edge on the map, and it has three regimes, all of them measured rather than described. Down to −15 nothing breaks: a negative edge is not by itself a problem. From −16 to −50 Dijkstra answers 93 where the truth is 92, then 78, then 58 - always too large, because a closed vertex is never reopened - and the true route appears beside the yellow one so the error is visible rather than asserted. At −51 a negative cycle appears: there is no shortest path at all, Bellman-Ford says so, and Dijkstra prints the same 93 with a straight face.
Equations used in the module
Equations terrain on an m x m grid, each cell priced 1..9, a step costs the price of the cell you enter; start top left, goal bottom right with non-negative weights Dijkstra is right - checked against Bellman-Ford relaxed to a fixed point, and on 3x3 and 4x4 against a FULL enumeration of simple paths flat terrain has a closed form: cost to (i, j) = w(i + j), so the goal costs w·2(m−1) - 120 for w = 5, m = 13 settled vertices = m² (each closed exactly once); relaxations = edges = 4m(m−1) = 624 at m = 13; heap pushes 169 on the default terrain default 13x13, discount off: cheapest route to the goal 93, the same 93 from Bellman-Ford, 25 cells in the route, 0 cells where the two disagree one directed discount edge from (0,7) to (5,0), and the slider has THREE regimes, all measured: down to −15: no error at all - a negative edge is not by itself a problem −16 to −50: Dijkstra returns 93 while the truth is 92, 78, 58 - always TOO LARGE, and the answers disagree on 65, 122, 159 of the 169 cells −51 and below: a negative cycle - there is no shortest path, Bellman-Ford says so, and Dijkstra still prints 93 the ends of the discount edge were chosen by enumerating all pairs: the window needs d(far) − d(near) < k < cost(near to far), and it is empty when the cheap route to the far cell runs through the near one
