Algospot - 1261
This makes it easier when writing Dijkstra on a grid.
Say a graph has nodes A, B, and C. Given some starting node,
say the shortest distance to A is 2.
Say the shortest distance to B is 3.
The priority queue pops in order of the smallest shortest path.
So A is popped first, then B.
And say A and B each have an edge that goes directly to C. Here,
say the cost of the edge connecting A and C is 4.
Say the cost of the edge connecting B and C is 2.
First, when A is popped, the shortest distance to C is updated to 2 + 4 = 6.
(Here the shortest distance to B is 3 and to C is 6, so B is popped before C)
Then when B is popped, the shortest distance to C is updated to 3 + 2 = 5.
Once B has been popped, the priority queue holds 2 entries for C.
One says the distance to C so far is 6,
and the other says the distance to C is 5.
Here the first entry for C is larger than the most recently updated shortest distance,
so you have to prevent the unnecessary work of iterating over C's edges.
But in this Algospot problem, that check itself is unnecessary.
Because say there's some node X, and a, b, c each have an edge connecting to X.
Then the cost of the edge from a, b, c to X is always the same.
No matter which node you move from, you either break a wall or you don't.
( Let f(n) be the shortest distance from the starting point to node n. )
Analyzing in more detail, if a, b, c were popped from the priority queue in that order,
f(a) <= f(b) <= f(c).
The shortest distance to X from each of a, b, c is
f(a), f(b), f(c) or f(a)+1, f(b)+1, f(c)+1, so
The shortest distance to a node equals the value that was updated first.
— Conclusion
Using this, you can run Dijkstra more simply.
Here are problems where you can apply this.
The one in green is Zelda, right? - 4485
4485: The one in green is Zelda, right?
Making a Maze - 2665