Does A * work with negative weight as long as the heuristic is valid?

Question

It seems true, but I can’t find anyone on the Internet saying that it is, so I would like to make sure. Please tell me if you agree, and if so, why. Ideally, a reference to paper or, if you do not agree, a counterexample.

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

First of all, if G has negative cycles that are reachable from the source and achieve the goal, there is no valid heuristic, since it is impossible to underestimate the cost of achieving the goal, because it is -∞ .

If there are no such cycles, there may be a valid heuristic. In particular, the sum of all negative edges will always underestimate the cost of achieving the goal.

I get the impression that in this case A * might work fine.

PS I could run Bellman-Ford on the chart, detect negative cycles, and if there are none, outweigh to get rid of the negative edges. But, if I know that there are no negative loops, I can just skip this and run A *.

---

This is trivially wrong. The value of the peak is the sum of the heuristic and the path built so far ... while the heuristic underestimates the cost of achieving the goal, the sum of the heuristic and the path traveled so far cannot. Maxima culpa.

It seems that sorting an open set with a function that underestimates the cost of achieving the goal, while passing through a given vertex may work, although ... if <sum of negative edges in the graph> used as such a function, it looks like degenerate bypassing the schedule.

Answer 1

Consider an example with three nodes and three weights:

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

From 1 to 2 there is a path with a weight of -10. So, you will get this first and set it as the minimum path to 2. However, there is a path (1-3-2) that is less than the first.

Answer 2

In the example given by the highest answer: (2, -10) goes into the priority queue. Agreed. In the same way (3, x), where x <= - 11, since heuristics are valid. Now (3, x) is set as x <-10, and we get the right solution.

I cannot express this as a comment, because I do not have enough reputation.

Answer 3

This is trivially wrong. The top value is the sum of the heuristic and the path built so far ... while the heuristic underestimates the cost of achieving the goal, the sum of the heuristic and the path traveled so far cannot be.

A * will never extend a node in such a way that the sum of the heuristic and the traversed path (f-value) is greater than the optimal path length. This is due to the fact that along the optimal path there always exists one node with an f-value less than or equal to the optimal cost.

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