3

According to a.o. this accepted answer, Dijkstra's algorithm is a special case of the A* algorithm.

Special case

In logic, especially as applied in mathematics, concept A is a special case or specialization of concept B precisely if every instance of A is also an instance of B but not vice versa, or equivalently, if B is a generalization of A.

There are, however, cases that produce different results for A* with a constant zero heuristic when compared to Dijktra's algorithm.

One of these is their behaviour when the graph contains negative cycles: while A*'s closed set handling completely avoids such cycles, Dijkstra's follows negative cycles infinite times before proceeding.

Another edge case where their results may differ, this time even with an admissible heuristic, is when A* underestimates the cost of the final edge in a graph. Given a graph like this: graph with nodes A, B, C, D

Most A* implementations, including the psuedo-code example at wikipedia, would incorrectly assume A-B-D to be the shortest path if the heuristic function for rates B to D below 2, while Dijkstra correctly yields A-C-D.

Can Dijkstra's algorithm still be viewed as special case for A*, given the above?

Stratadox
  • 1,291
  • 8
  • 21
  • 2
    I'm not sure what you mean by »*A\*'s closed set handling*«. If there is a negative cycle (or even just any negative weight) and you are using the heuristic »*h(e)=0 for all edges e*« then *h* is not admissible and A\* won't compute optimal paths. Maybe Dijkstra's algorithm is a specialization of A\* *with an admissible heuristic* but certainly not a specialization of A\* *with an inadmissible heuristic*. – Socowi Feb 21 '19 at 22:09
  • Heh, I hadn't even considered the admissibility! Good point (you could convert it into an answer, I'd argue). With closed set handling I refer to the fact that A* will skip any node it had already visited, thus avoiding loops. – Stratadox Feb 21 '19 at 22:20
  • Updated the question with a differing result using an admissible heuristic. – Stratadox Mar 02 '19 at 15:34
  • 1
    @Stratadox In the graph above, A* with the heuristic »*h(e)=0 for all edges e*« yields the same result with Dijkstra's, i.e. A-C-D. It does not assume A-B-D to be the shortest path. – Gorisanson Jul 09 '20 at 10:21
  • @Gorisanson can you demonstrate this? The pseudocode on the wikipedia article would consider B as first option (cost 2 vs 4) and schedule D as next option with a priority of 2 (cost of B + h(D) = 2), run the next iteration and find that D == goal: path detected. If I'm mistaken, please correct me, but this explanation fits my unit test results. – Stratadox Nov 28 '20 at 20:59
  • 1
    @Stratadox Let me explain the procedure of A* algorithm with the heuristic *»h(e)=0 for all edges e«* for the graph. The pseudocode on the wikipedia article would consider A as first option and calculate `fScore` for B (cost 2) and C (cost 4). And it consider B as next option (B: cost 2 vs C: cost 4) and calculate `fScore` for D (cost 12). And now, it consider C as next option (C: cost 4 vs D: cost 12) and calculate `fScore` for D (cost 8). And it consider D as next option and if finds that D is the goal: path detected. So it finds A-C-D as the shortest path with cost 8. – Gorisanson Nov 29 '20 at 08:47

0 Answers0