Add to Chrome
Add to Edge
Add to Firefox
Add to Opera
Add to Brave
Add to SafariWhen comparing Dijkstra's Algorithm vs Breadth-first search, the Slant community recommends Dijkstra's Algorithm for most people. In the question“What are the best 2D pathfinding algorithms?” Dijkstra's Algorithm is ranked 2nd while Breadth-first search is ranked 3rd. The most important reason people chose Dijkstra's Algorithm is:
Dijkstra is an uninformed algorithm. This means that it does not need to know the target node beforehand. For this reason it's optimal in cases where you don't have any prior knowledge of the graph when you cannot estimate the distance between each node and the target.
Question Ranking
Pros
Pro Uninformed algorithm
Dijkstra is an uninformed algorithm. This means that it does not need to know the target node beforehand. For this reason it's optimal in cases where you don't have any prior knowledge of the graph when you cannot estimate the distance between each node and the target.
Pro Good when you have multiple target nodes
Since Dijkstra picks edges with the smallest cost at each step it usually covers a large area of the graph. This is especially useful when you have multiple target nodes but you don't know which one is the closest.
Pro Complete
BFS is complete, which means that it will always find a solution if it exists.
Pro Optimal for finding the shortest path in a graph
BFS is very useful when you want to find the shortest and most optimal path by traversing as few edges as possible.
Cons
Con Fails for negative edge weights
If we take for example 3 Nodes (A, B and C) where they form an undirected graph with edges: AB = 3, AC = 4, BC=-2, the optimal path from A to C costs 1 and the optimal path from A to B costs 2. If we apply Dijkstra's algorithm: starting from A it will first examine B because it is the closest node. and will assign a cost of 3 to it and therefore mark it closed which means that its cost will never be reevaluated. This means that Dijkstra's cannot evaluate negative edge weights.
Con Requires a large amount of memory
When traversing one tree level, you need a way to know which nodes to traverse once you get to the next one. The way this is done is by storing the pointers to a level's child nodes while searching it. The pointers are stored in a FIFO way, this means that BFS needs a relatively large amount of memory in order to store the pointers. The amount of course depends on the complexity of the graph tree and the amount of nodes and/or levels.
