Have a look at:

   Simon Peyton Jones on Getting from A to B fast route finding on slow computers [PWL London]
   https://www.youtube.com/watch?v=L1XDdy-hOH8

It goes from 0 all the way up to A*, then beyond. I think the new stuff is based on https://www.cs.tau.ac.il/~haimk/papers/sp-wea.pdf but I'm not sure since the paper isn't explicitly named in the video.