Spent some time today trying to replace difftastic's implementation of Dijkstra's algorithm with A* search.
I got a working implementation that passes tests: https://github.com/Wilfred/difftastic/commit/9a271169f68cdb678efe2035f5a4e45daeb6533d but sadly it's no faster. My slowest files still take 1.5 seconds with similar memory.