Search code examples
algorithmgraphshortest-path

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

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)?

Solution

  • 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:

    enter image description here

    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|𝑉|).