The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal. The bidirectional case of A* is not as simple as the bidirectional Dijkstra as the finish condition is a bit tricky, of course you can manage to implement it if you work with consistent potential functions (see paper reference below).Now to my question: when implementing a special distance estimate for A* (landmarks/ALT) this works also in the bidirectional case. In some papers they say one can change the active set of landmarks while the search is going on. This makes sense as the estimates will get better and still only a subset is involved for the estimate.But will changing/improving the distance estimate while the search is going influence the optimality? Unintuitive things can follow from this, e.g. a distance update to a node lowers the distance from source to this node but could increase the distance from this node to the goal due to the better distance estimate but I'm unsure if this violates the 'consistent potential' definition and could result in suboptimal paths. (E.g. in my latest trial to implement this I sometimes get suboptimal results but this could be also other bugs.)The paper Computing Point-to-Point Shortest Paths from External Memory says I can do so but I'm unsure if I misunderstood something: 6.1 Restarting. As we shall see below, we sometimes need to change the way lower bounds are calculated in the middle of an ALT computation,  e.g., by replacing the current potential functions p f and p r by  another consistent pair.
Bidirectional A*: is an update of the distance estimation feasible while searching?
graph theory;graph algorithms