I've started playing again with A* search instead of Dijkstra for difftastic. So far it's only saved me visiting 3% of graph nodes, which is negligible.
A* works best when you have a good heuristic, but finding a good heuristic is hard. Currently: https://github.com/Wilfred/difftastic/blob/3b9474d9fe360a4122d63efbecda2ac7b3b36d30/src/diff/dijkstra.rs#L39