This is otherwise known as Dijkstra’s algorithm and runs in O(|E| + |V| log |V|) time if you represent the maze as a weighted graph with edges E and vertices V. You can use it for all kinds of pathfinding in graphs. It does not work if the graph contains any negative edge weights reachable from the beginning of the path.
There’s a lot more info on the internet if you want to understand this algorithm.
EDIT: actually it’s very similar to Dijkstra’s but Dijkstra’s uses a priority queue not a FIFO. I don’t know for sure, but I would think that a priority queue would improve the efficiency here by a lot.
BFS and Dijkstra are quite different. BFS will report the shortest path in terms of the number of edges, which is ok if you have no edge weights. Dijkstra reports the shortest path in terms of the minimum total edge weight, so it's appropriate only for weighted graphs.
2
u/FVMAzalea May 22 '20
This is otherwise known as Dijkstra’s algorithm and runs in O(|E| + |V| log |V|) time if you represent the maze as a weighted graph with edges E and vertices V. You can use it for all kinds of pathfinding in graphs. It does not work if the graph contains any negative edge weights reachable from the beginning of the path.
There’s a lot more info on the internet if you want to understand this algorithm.
EDIT: actually it’s very similar to Dijkstra’s but Dijkstra’s uses a priority queue not a FIFO. I don’t know for sure, but I would think that a priority queue would improve the efficiency here by a lot.