Does A* work with negative weights as long that the heuristic is admissible?

Question

This seems true but I can't find anyone on the internet saying it is, so I'd like to make sure. Please tell me if you agree and if so, why. Ideally a link to a paper, or, if you disagree, a counterexample.

Let G be a directed graph with some negative edges. We want to run A* on G.

First off, if G has negative cycles reachable from the source and reaching the goal, there is no admissible heuristic, as it's impossible to underestimate the cost of reaching the goal because it's -∞.

If there are no such cycles however, there may be some admissible heuristic. In particular, the sum of all negative edges will always underestimate the cost of reaching the goal.

I'm under the impression that in this case, A* may work just fine.

P.S. I could run Bellman-Ford on the graph, detect negative cycles, and if there are none, reweigh to get rid of negative edges. But, if I know there are no negative cycles, I can just skip that and run A*.

---

This is trivially wrong. The cost of a vertex is the sum of the heuristic and the path built so far... while the heuristic underestimates the cost to reach the goal, the sum of the heuristic and the path taken so far may not. Maxima culpa.

It seems that sorting the open set with a function that underestimates the cost to reach the goal, while going through a given vertex may work though... if one uses <sum of negative edges in the graph> as such a function, it looks like it degenerates into a graph traversal.

Answer 1

Consider the example with 3 nodes and 3 weights:

1 2 -10
1 3 -3
3 2 -8

From 1 to 2 there is path with weight -10. So you get this first and establish it as the minimal path to 2. However there is path (1-3-2) which is smaller than the first one.