Does Dijkstra's algorithm work with negative edges if there is no "processed" check?

Question

Typically, in Dijkstra's algorithm, for each encountered node, we check whether that node was processed before attempting to update the distances of its neighbors and adding them to the queue. This method is under the assumption that if a distance to a node is set once then the distance to that node cannot improve for the rest of the algorithm, and so if the node was processed once already, then the distances to its neighbors cannot improve. However, this is not true for graphs with negative edges.

If there are no negatives cycles then if we remove that "processed" check, then will the algorithm always work for graphs with negative edges?

Edit: an example of a graph where the algorithm would fail would be nice

Edit 2: Java code https://pastebin.com/LSnfzBW4

Example usage:

3 3 1 <-- 3 nodes, 3 edges, starting point at node 1
1 2 5 <-- edge of node 1 and node 2 with a weight of 5 (unidirectional) 
2 3 -20 <-- more edges
1 3 2

Newsy

Could you please provide pseudocode or code? Without the "processed" check, then when this algorithm will stop? I'm afraid that without the "processed" check, the runtime will be worse compared to the Bellman-Ford algorithm. Maybe exponential runtime, because no pruning happens at all. – Chary

Java code added! – Newsy

Answer 1

The algorithm will produce the correct answer, but since nodes can now be visited multiple times the time complexity will be exponential.

Here's an example demonstrating the exponential complexity:

w(1, 3) = 4
w(1, 2) = 100
w(2, 3) = -100
w(3, 5) = 2
w(3, 4) = 50
w(4, 5) = -50
w(5, 7) = 1
w(5, 6) = 25
w(6, 7) = -25

If the algorithm is trying to find the shortest path from node 1 to node 7, it will first reach node 3 via the edge with weight 4 and then explore the rest of the graph. Then, it will find a shorter path to node 3 by going to node 2 first, and then it will explore the rest of the graph again.

Every time the algorithm reaches one of the odd indexed nodes, it will first go to the next odd indexed node via the direct edge and explore the rest of the graph. Then it will find a shorter path to the next odd indexed node via the even indexed node and explore the rest of the graph again. This means that every time one of the odd indexed nodes is reached, the rest of the graph will be explored twice, leading to a complexity of at least O(2^(|V|/2)).

Tetrahedron

Answer 2

If negative edges release from start node, dijkstra's algorithm works. But in the other situation Usually it dosen't works for negative edges.

Breakthrough

Could you provide an example, please? – Newsy

@davidSC A---(5)--->B----(-20)-->C & A----(2)--->C it's not ok because negative edge dosen't release from start nod(A) but in this example: A---(-7)---->B----(1)-----C && A---(-5)--->C dijkstra's algorithm works – Breakthrough

I attached Java code in the original post. If you try that example (assuming all paths are unidirectional), the algorithm still works. – Newsy

Answer 3

If I understand your question correctly, I don't think its possible. Without the processed check the algorithm would fall into infinite loop. For example, for a bidirected graph having two nodes i.e. a and b with one edge from "a" to "b" or "b" to "a", it will first insert node "a" inside the priority queue, then as there have an edge between "a" to "b", it will insert node "b" and pop node "a". And then as node "a" is not marked processed for node "b" it will again insert node "a" inside the priority queue and so on. Which leads to an infinite loop.

For finding shortest path in the graphs with negative edges Bellmen-ford algorithm would be the right way.

Ballast

Dijkstra's algorithm will only put nodes into the priority queue if the distance to that node had been reduced. Even without a processed check, there's only so many times that the distances can be improved, so the algorithm will not go into an infinite loop unless there is a negative cycle, in which case the distances will never stop improving. – Newsy

yes you are right, it wont get into infinite loop but it would definitely run longer than usual and in that case might produce the correct answer! – Ballast