I've factored out the Vector and Edge definitions in difftastic so I can experiment with different graph search algorithms! It's so much easier when you can toggle between them.
So far A* is only 10% faster than Dijkstra, but I've found an additional 20% win that benefits all :)