A* with a consistent heuristic is Dijkstra on a modified graph whose edge weights are the original edge weights plus f(target) - f(source) where f is the A* "he

A* with a consistent heuristic is Dijkstra on a modified graph whose edge weights are the original edge weights plus f(target) - f(source) where f is the A* "heuristic". If the heuristic is not consistent, the edge weights aren't necessarily nonnegative, but you can still use the "hybrid Bellman–Ford–Dijkstra algorithm", which is a generalization of Dijkstra that works for all graphs, and should be asymptotically better than naive A*.