Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity

Question

It is commonly stated (like here) that Dijkstra's algorithm does not work for graphs with negative weights.

But what if we just modify this algorithm a little bit? Suppose we have a hashmap where the cost of each node is stored, and we also have a hashset where all the processed nodes are contained. If we find a shorter path to an already processed node, then we remove it from the list of processed nodes and add it to the heap again.

In my opinion, the time complexity of such a modified algorithm will differ only by a constant; could you please explain if I am wrong?

If I'm right about the unchanged time complexity, then why is it said that Dijkstra's algorithm is not applicable to graphs with negative weights, if we can use such a modification, and then make it work for negative edges too (assuming no negative cycles)?

Answer 1

In my opinion, the time complexity of such a modified algorithm will differ only by a constant, please explain if I am wrong

It can differ more than a constant. Here is a category of graphs for which we get a worse time complexity:

Graphs of this category have 2−1 nodes, numbered from −+1 to −1. The paths from node 0 to node 1 have a decreasing cost as we go "down" first (to nodes -1, -2, -3...) and then back up to node 1.

If we perform Dijkstra's algorithm with source at node 0, the first nodes to expand will be nodes 1 to −1, giving a cost of −1 to reach that rightmost node.

Then node -1 will be expanded, and so the same nodes 1 to −1 will be put on the priority queue again ... giving a reduced cost of −2 to get to that rightmost node.

And so it continues: node -2 will get involved, then node -3, ... until the node at the bottom gets involved. Each time the nodes 1 to −1 would have to be put back on the queue.

So for this subset of graphs (with varying ) the time complexity is O(²) = O(||²), which is worse than what Dijkstra's algorithm ensures for these graphs if they would have the same shape, but no negative weights. Then Dijkstra's algorithm would do the job in O(||log||).

Answer 2

I answered here yesterday: https://stackoverflow.com/a/77985985/5884011

Short answer is, you can, but it's not the original Dijkstra's algorithm anymore, it's a variant of it. Remember, the original algorithm is theory based, so it wasn't written like I am going to use a heap/hash do this first then etc. It was written more like the shortest path of any node v is the shortest path to u (the one before it), plus the distance of (u,v) and bunch of proofs why this is correct.

So the hypothesis to start with is anything before v is shortest already. By having a negative edge, you break the assumption that anything before it is the shortest, because from s -> u -> v, even tho u is before v, s -> v is shorter than s -> u.

To Add:

the core problem of negative edge is never about what do I use to keep my stuff, heap, hash, how do I keep it etc. It's the fact you have to run through all edges multiple times. Regardless what you use if you don't do O(V*E) you can't solve it. So it's not a constant factor, and which is why after modifying literally how it works is no longer called the Dijkstra's algorithm, because that's not what the original algorithm is.

Answer 3

Here's a very simple, intuition-level argument for why such an algorithm can never be equivalent to Djikstra:

Suppose in some huge graph, your target is one edge away from your origin, and that's the lightest-weight edge from your source. I claim it's an intrinsic property of Djikstra that the algorithm will not even look at the rest of the huge graph; it goes straight to the sink and returns immediately.

If negative edge weights are allowed, this is not safe; there could be some sequence of negative edges elsewhere in the graph which could result in a lower-weight total path, so the entire graph must be considered.

This case may seem contrived, but it speaks to the heart of Djikstra's algorithm - the growing set of nodes for which we know we have found the shortest path, which we expand as we consider additional nodes. If negative edge weights are allowed, this set cannot have any members - we can never know we've found the lowest-weight path until we've inspected every edge.