Dijkstra's algorithm with negative edges on a directed graph

Question

What if the only negative edge costs are coming from the initial node? Will the algorithm still work?

I feel like yes, because I can't think of a counter-example, but I'm having trouble proving it. Is there a counter-example?

Negative edges are a problem for Dijkstra's because there's no guarantee that the edge you pick produces the shortest path if there is an edge you can pick later that is largely negatively weighted. But if the only negative edges are coming out of the initial node, I don't see the problem.

I'm not looking for an algorithm. I'm looking for some insight into the Dijkstra's.

I'm talking about a directed graph, if that makes a difference.

Answer 1

The trouble with having a negative-cost edge is that you can go back and forth along it as many times as you like.

If you impose a rule that an edge may not be used more than once, you still have a problem. Dijkstra's algorithm involves marking a node as "visited", when it's distance from the initial node is considered know once and for all. This happens before all of the edges have been examined; the shortest path from the initial node to node X has been found, all other paths from the initial node are already longer than that, nothing that is discovered later can make those paths shorter. But if there are negative-cost edges somewhere, then a later discovery can make a path shorter, so it may be that a shorter path exists which Dijkstra will not discover.

If only the edges that connect to the initial node may have negative costs, then you still have problem, because the shortest path might involve revisiting the initial node to take advantage of the negative costs, something Dijkstra cannot do.

If you impose another rule that a node may not be visited more than once, then Dijkstra's algorithm works. Notice that in Dijkstra's algorithm, the initial node is given an initial distance of zero. If you give it some other initial distance, the algorithm will still find the shortest path-- but all of the distances will be off by that same amount. (If you want the real distance at the end, you must subtract the value you put in.)

1. So take your graph, call it A, find the smallest cost of any edge connected to the initial node, call it k which will be negative in this case).
2. Make a new graph B which you get by subtracting k from the cost of each edge connected to the initial node. Note that all of these costs are now non-negative. So Dijkstra works on B. Also note that the shortest path in B is also the shortest path in A.
3. Assign the initial node of B the distance k, then run Dijkstra (this will give the same path as running with an initial distance of zero). Compare this to running Dijkstra naively on A: once you leave the initial node everything's the same in the two graphs. The distances are the same, the decisions are the same, the two will produce the same path. And in the case of A the distace will be correct, since it started at zero.

Answer 2

Counter-example:

Graph G = (V, E), with vertices V = {A, B}, edges E = {(A, B), (B, A)} and weight function w(A, B) = -2, w(B, A) = +1.

There's a negative weight cycle, hence minimum distances are undefined (even using A as initial node).