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

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, 开发者_Python百科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.

---

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.

---

In the example given by top rated answer: (2,-10) goes into priority queue. Agreed. So does (3,x) where x<=-11 as heuristic is admissible. Now (3,x) gets popped as x<-10 and we get to the correct solution.

I can't put this as a comment as I don't have enough reputation.

---

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.

A* will never expand a node such that the sum of the heuristic and the path taken so far (f-value) is greater than the optimal path length. This is because, along the optimal path, there is always one node with f-value less than or equal to the optimal cost.

Thus, even with negative-weight edges, A* will find the optimal path if such a path exists, as long as there are finite number of edges with f-value less than the optimal cost.