0

I'm developing a GPS system. The aim is to develop algorithms that are more appropriate to solve the problem. I'm using Dijkstra and A* and now on my report I need to make some theory around it and show which one is the best.

I have a map full of vertexes and edges (streets), and I'd like to know how do I compare both algorithms in a way I can show why one is better than the other and why.

I'm asking this because when I run Dijkstra it will get the path for all vertexes so it's probably the same even if I increase the path between the points I want to know which is the way I thought would be good to test A*. Is there a way I can get a comparable term?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Perseverance
  • 337
  • 5
  • 18

1 Answers1

1

A star is basically informed variation of Dijkstra. And A star uses breadth-first search to speed the search which would be a greedy approach.

Final cost = movement cost + heuristic cost

The above equation is used for the A star algorithm. It is similar to Dijkstra's algorithm. So, you can compare it with the speed. Still mind when N increases, using A Star would not be the best. Because it selects the optimal path if possible under two conditions:

  1. The estimated cost is always lower than real cost.
  2. Enough memory is available for to find a solution and represent it.

It is explained in another Stack Overflow question, Difference and advantages between Dijkstra & A star.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Michael Marshal
  • 19
  • 6