Skip to content

Compare methods

Compare source explanations, strengths, limitations and references for up to four methods.

7 results
Criterion A-star Search Algorithm Dijkstra Algorithm Bellman-Ford Algorithm
Overview
  • The A* Search Algorithm, developed by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in 1968, is an optimal path-finding algorithm that combines the benefits of Dijkstra's algorithm with heuristic guidance. It efficiently finds the shortest path by balancing actual distance from the start with estimated distance to the goal.
  • Dijkstra's Algorithm, introduced by Edsger W. Dijkstra in 1956, is one of the most fundamental algorithms in computer science for solving the single-source shortest path problem. It finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative edge weights.
  • The Bellman-Ford Algorithm, developed by Richard Bellman and Lester R. Ford in the 1950s, is a fundamental algorithm for computing shortest paths in weighted graphs that may contain negative edge weights. Unlike Dijkstra's algorithm, it correctly handles negative weights and can detect the presence of negative-weight cycles.
Use and interpretation
  • Apply A* when you need to find optimal paths in graphs where a good heuristic function is available. It is particularly effective for pathfinding in games, robotics, and route planning where informed search can substantially reduce computation. Use it when speed matters but optimality is required. For cases without a reliable heuristic, use Dijkstra's algorithm instead.
  • Apply Dijkstra's algorithm when finding shortest paths in graphs with non-negative edge weights. It is ideal for navigation systems, network routing, and any graph problem requiring optimal paths. Use it for single-source shortest paths to all vertices. For graphs with negative weights, use Bellman-Ford instead. For bidirectional search or heuristic guidance, consider A* algorithm.
  • Apply the Bellman-Ford algorithm when computing shortest paths in graphs with negative edge weights. It is essential for currency arbitrage detection, network protocols where weights can be negative, and any application where negative costs or weights are meaningful. Use Dijkstra's algorithm if all weights are non-negative, as it is more efficient. For detecting negative cycles without computing paths, this algorithm is also appropriate.
Strengths
  • Optimal pathfinding when the heuristic is admissible
  • Much faster than Dijkstra or breadth-first search when good heuristics are available
  • Flexible: works with any admissible heuristic function
  • Well-suited for single-goal pathfinding problems
  • Extensive real-world validation in games, robotics, and navigation systems
  • Simple to understand and implement with clear correctness guarantees
  • Efficient with proper data structures: O((V+E)logV) with binary heap, O(V²) with array
  • Optimal for non-negative weight graphs; proves optimality of computed paths
  • Works on both directed and undirected graphs
  • Foundation for numerous extensions and related algorithms
  • Handles graphs with negative edge weights correctly
  • Detects negative-weight cycles, preventing erroneous shortest path results
  • Simpler to understand and implement than some advanced shortest path algorithms
  • Guaranteed to find shortest paths in O(VE) time
  • Works on both directed and undirected graphs (with caution on undirected)
Limitations
  • Optimality depends on the admissibility of the heuristic function
  • Performance degrades significantly with poor or inadmissible heuristics
  • Memory usage can be substantial in large search spaces (maintains open and closed sets)
  • Requires explicit domain knowledge to design good heuristic functions
  • Cannot handle graphs with negative edge weights
  • Computes shortest paths to all vertices, not just one destination (though can terminate early)
  • Less efficient than A* when heuristic information is available
  • Requires all vertices to be discovered; inefficient for very sparse connectivity
  • Slower than Dijkstra for non-negative weights: O(VE) versus O((V+E)logV)
  • Less efficient for sparse graphs compared to other algorithms
  • Requires all edges to be explicitly listed, making it less suitable for implicit or dynamic graphs
  • No heuristic guidance available to speed up computation
Common pitfalls
  • Using an inadmissible heuristic that overestimates costs, leading to suboptimal paths
  • Choosing a heuristic that is too simple or unrelated to the problem, reducing search efficiency
  • Inefficient implementation of the open set (should use priority queue), causing slow node selection
  • Using the algorithm on graphs with negative weights, resulting in incorrect shortest paths
  • Inefficient implementation with linear time extract-min operation, leading to poor performance
  • Failing to properly update distances when neighbors are revisited through different paths
  • Forgetting to perform the additional iteration to detect negative cycles
  • Assuming the algorithm works correctly in undirected graphs with negative edges (can create virtual negative cycles)
  • Using the algorithm when Dijkstra is sufficient, resulting in unnecessary performance loss
Introduced by
  • Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
  • Edsger W. Dijkstra
  • Richard Bellman and Lester R. Ford
Year
  • 1968
  • 1956
  • 1956