title: Is A* really better than Dijkstra in real-world path finding?
body: <p>I'm developing a path finding program. It is said theoretically that A* is better than Dijkstra. In fact, the latter is a special case of the former. However, when testing in the real world, I begin to doubt that is A* really better?</p>
  
  <p>I used data of New York City, from <em><a href="http://www.dis.uniroma1.it/challenge9/download.shtml">9th DIMACS Implementation Challenge - Shortest Paths</a></em>, in which each node's latitude and longitude is given.</p>
  
  <p>When applying A*, I need to calculate the spherical distance between two points, using <a href="http://en.wikipedia.org/wiki/Haversine_formula">Haversine Formula</a>, which involves sin, cos, arcsin, square root. All of those are very very time-consuming.</p>
  
  <p>The result is,</p>
  
  <p>Using Dijkstra: 39.953&nbsp;ms, expanded 256540 nodes.</p>
  
  <p>Using A*, 108.475&nbsp;ms, expanded 255135 nodes.</p>
  
  <p>Noticing that in A*, we expanded less 1405 nodes. However, the time to compute a heuristic is much more than that saved.</p>
  
  <p>To my understanding, the reason is that in a very large real graph, the weight of the heuristic will be very small, and the effect of it can be ignored, while the computing time is dominating.</p>