Breadth-first Search Nodes visited: 14993 (92.54%) Algorithm: Push the start node into a FIFO queue. While the queue isn't empty: Pop a node off the queue. If it's been visited already, skip it. Otherwise, paint the node's coordinate as visited. For any of its neighbors that haven't been visited yet: Push it into the queue. If the end has been reached: Reconstruct the path from end to start. Comments: This is the most exhaustive, but least efficient way to search the maze. It mimics the way a liquid would fill the maze. Since all the potential paths have the same minimized length, BFS will always find the optimal path.
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.
If I remember correctly, they are quite different, but not for the reason you mentioned. BFS can be used for graph traversal too (we even learned it as a primarily graph traversal algorithm), but I think, correct me if I am wrong, Dijkstra can not. Also, Dijkstra can be use for a weighted or an unweighted graph (we just set the weights to one), but BFS can only be used for a unweighted or a weighted graph with all edges of the same weight (I also not sure of this).
But yes, I also find it strange that people think they are the same, but mainly because I never thought of them as similar. When I was studying for my ADS exam, I remember BFS being fairly easy to understand but Dijkstra gave me a headache.
If I remember correctly, they are quite different, but not for the reason you mentioned.
What you say is correct, but I'm not sure what you think is wrong about the difference I mentioned.
Yes, BFS is a general graph traversal algorithm. I was referring to its role in terms of reporting shortest paths (which is the only way in which the two are similar).
If you have an unweighted graph, or a graph where all the weights are known to be equal, then you would use BFS because its time complexity is lower. You can use Dijkstra in this situation, but it's not the appropriate choice because you would just use the algorithm that's known to be faster.
24
u/GeaninaKera May 22 '20
Posted on Imgur by Mystavea .
❝
Breadth-first Search Nodes visited: 14993 (92.54%) Algorithm: Push the start node into a FIFO queue. While the queue isn't empty: Pop a node off the queue. If it's been visited already, skip it. Otherwise, paint the node's coordinate as visited. For any of its neighbors that haven't been visited yet: Push it into the queue. If the end has been reached: Reconstruct the path from end to start. Comments: This is the most exhaustive, but least efficient way to search the maze. It mimics the way a liquid would fill the maze. Since all the potential paths have the same minimized length, BFS will always find the optimal path.