3 ms·

I think A* is solving a different problem than dijkstra's, since it requires an admissible heuristic to do any better than dijkstra's. As long as you have an a

• jvanderbot 2y ago
  A* is not solving a different problem. What happens if h(x)=0 for all x in A*?
  • Jtsummers 2y ago
    > A* is not solving a different problem. A* finds the shortest path from a node to a single other node. Dijkstra's finds the shortest paths from a node to all other nodes. If you use it as a search algorithm to find the shortest path to a single target, then yes, it's equivalent to A* with h(x)=0, but you're terminating Dijkstra's early (once your target is found) and not running the full algorithm.
  • foota 2y ago
    A different problem in the sense that A* is useless (it degrades to dijkstra's) when there is no admissible heuristic. So I think it's reasonable to say that A* solves a different problem (namely, path finding when there is an admissible heuristic), since when there's no admissible heuristic it is identical to dijkstra's.
• superjan 2y ago
  An example for those not in the know: to find a shortest route on a realworld map, an admissible heuristic would be that the minimum travel distance between two nodes will be a straight line. While examining options, A* takes this into account, Dijkstra does not.