Dijkstra vs A* resulting path

user_10286691 0
Viewed 848

When I run Dijkstra and A* on different graphs, because both are optimal algorithms, I should always expect to find the same path, right?

Like for the following graph:

Nodes: S, A, B,C, D, E, G

Edges and costs: (S, A)=1, (A, B)=1 (B,C)=1, (A,E)=8, (A, D)=6, (D, G)=2

heuristics: h(S)=6, h(C)=7, h(B)=6, h(A)=5, h(D)=2, h(E)=1, h(G)=0

I am finding S->A->D->G as path for both. The cost of this path is 9 for both Dijkstra and A*.

Is this always the case for any graph because both are optimal? If I want to compare these two algorithms, what should I use as statistics, time seems to be the same as well?

Thanks.

a-star dijkstra artificial-intelligence
2 Answers

If the shortest path is unique, then any correct shortest path algorithm must find exactly that path.

On graphs where there are multiple paths between the start and the goal that have the same cost, even different implementations of the same algorithm are not guaranteed to find the same path, because there may be subtle differences in for example:

  • The order of processing outgoing edges from a node when it is "explored".
  • The order in which nodes of equal value are popped off of the priority queue.
  • For A*, different correct heuristics often result in different paths (of equal cost) due to ordering the priority queue differently.

If I want to compare these two algorithms, what should I use as statistics, time seems to be the same as well?

On big enough graphs and when you have a good heuristic, A* will eventually perform better. A common example is a grid without many impassable tiles, where Dijkstra will explore roughly in a circle but A* (if given a proper heuristic) will approximately aim right at the goal and explore only a "thick line". You can see this effect in action on this visualiation.

user_5550450

Is this always the case for any graph because both are optimal?

A* can be seen as an improved version of the Dijkstra algorithm. It can be faster because of the heuristic. But A* is optimal only if the heuristic function is admissible, otherwise A* can find a solution that is correct but possibly sub-optimal compared to Dijkstra. So the answer is yes if and only if you carefully choose you heuristic.

If I want to compare these two algorithms, what should I use as statistics, time seems to be the same as well?

It depends. Do you want to analyzes the quality of the resulting path of the algorithms or their execution speed ? If your heuristic is good (ie. admissible), only the execution time will change. You can implement both and measure the execution time. You can also analyze the number of nodes explored.

user_129395570
Related