I have a large graph G and a pair of nodes s,t.  I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent.Suppose I already know of a path whose length is guaranteed to be at most 1.1 times as long as the shortest path.  Does this help A* find the shortest path faster?  If so, how and why?  Can knowledge of this path be used to improve the running time of A*, reduce the number of nodes, or make the heuristic more accurate?One improvement I can see is to remove the all the nodes in the open list which exceed the current solution. But if the heuristic is weak, this wouldn't help in reducing the number of nodes to be explored in the open list. So, in what other ways one can use the knowledge of known path in hand to help A* terminate itself earlier than without the knowledge of known complete path.
Early termination of A* with weak heuristic if solution is known
algorithms;graphs;optimization;shortest path;heuristics