What is the best alternative to Breadth-first search?
Here’s the Deal
Slant is powered by a community that helps you make informed decisions. Tell us what you’re passionate about to get your personalized feed and help others.
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. See More
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. See More
Help millions of people make better decisions.
Each month, over 2.8 million people use Slant to find the best products and share their knowledge. Pick the tags you’re passionate about to get a personalized feed and begin contributing your knowledge.