is dijkstra an A* algorithm?

Question

After reading an article about A* algorithm, I figured out that without the heuristic A* is no more than Dijkstra algorithm. But later I got an idea that Dijkstra is just a special case of A* because the minimum some of cost that we take is also a kind of heuristic .

What turns me on to think about the problem is an exercise, where we're asked to implement an A* algorithm so get the shortest path in a maze where some node or entries has different weights or increase the length of the path higherly .

After implementing the algorithm, the tutor asked me to calculate the node visited to fetched with and without heuristic. Both numbers was equal that's why i get this note that without heuristic I have Dijkstra .

So the question is: is Dijkstra really a kind of A* ? What can A* that Dijkstra cannot ?

Answer 1

The A* algorithm algorithm can be seen as a generalisation of Dijkstra's algorithm, but there is one caveat: Dijkstra's algorithm can be used to efficiently find shortest paths to all nodes in a graph, so constructing a shortest paths tree, while the A* algorithm needs a target node as input.

If however the task is to find the shortest path to a single target node, and we choose an A* algorithm with ℎ(𝑛) = 0 for all nodes 𝑛 (where ℎ is the heuristic function), then it boils down to Dijkstra's algorithm.

what can A* that dijkstra cannot ?

If the heurstic function is well chosen, an A* algorithm may need to visit fewer nodes than Dijkstra's algorithm to find the shortest path.

Answer 2

Dijkstra's algorithm and A* are both examples of "best-first" graph searches, where a node is expanded when it is currently the "best" open node, as measured by some metric. For Dijkstra's, the metric is "lowest current g-cost". For A*, the metric is "lowest current g-cost plus heuristic cost".

Both are admissible metrics and will find the minimal cost to a given node. A* is guaranteed to be at least as performant (in terms of number of nodes expanded) as any admissible search algorithm could be given the heuristic.