1

I know this may be selected as duplicate (since I've already seen this one Negative weights using Dijkstra's Algorithm I think none of the answers in SO are what I am looking for. I am interested in solution with Dijkstra algorithm in Graph that has one negative edge, but that Dijkstra will still show correct solution. How would that graph look like? I can't imagine, or I'm not good enough to understand how Dijkstra handle negative edges at all. And I know that there is a Graph with negative edge that can be traversed with Dijkstra and still have the right path. Don't tell me to use Bellman-Ford or Johnson's algorithm please.

Community
  • 1
  • 1
Buzz Black
  • 53
  • 1
  • 6
  • 2
    Short answer: Dijkstra's algorithm is not guaranteed to work if the graph has negative weights. This does not mean it will fail always. – Henry Apr 22 '16 at 13:07
  • I know, but how would graph look with negative edge but Dijkstra still working? when it comes A--->B(weight 5)----->C(weight -1) Does it normally subtract those two, or mark as indefinitely? – Buzz Black Apr 22 '16 at 13:13

3 Answers3

0

In fact, Dijkstra's algorithm tries to find the shortest path by comparing paths cost that can reach the goal and takes the path with the lowest cost. So it basically saves the lowest cost from starting point to every single node that can get you to the goal. it does that by comparing the new cost to a node and the last one, so if the negative value does not affect that order (the negative edge is a part from the shortest path) there is no problem with the path (but you get the wrong path cost). There is also the case where the negative edge can't lead you to the goal (it is not part of any path), then you have no problem in the path and the cost. Maybe you can find a third exemple, the edge is a part of one of the paths that takes you to the goal but it is still not part of the shortest path. Hope this helped, Good Luck.

Najj
  • 31
  • 4
0

If the absolute value of the negative edge is smaller than the weight of any other edge in the undirected graph, then Dijkstra's algorithm will work fine.

This ensures that we will not have the situation where the distance to a node that was popped out of the queue will be updated later. As in the typical settings (only positive weights), once we pop a node out of the queue, we are guaranteed that we can not reach it through a shorter path.

Note: this does not hold for directed graphs, where it is possible to encounter the source endpoint of the negative edge after the destination endpoint was popped from the queue (and thus may need to update a node that was popped).

danbanica
  • 3,018
  • 9
  • 22
  • So that's the way we look at the negative edge? We don't subtract it, but use absolute value of it? Is that how Dijkstra deals with negative weights? – Buzz Black Apr 22 '16 at 13:55
  • No, the negative value will be added (as usual), i.e. its absolute value is subtracted. If the condition mentioned at the top is true, then the algorithm will output the correct path. – danbanica Apr 22 '16 at 13:58
  • "Is that how Dijkstra deals with negative weights?" -- Dijkstra algorithm is not designed for negative weights, thus it does not have a specific way to deal with them. I just tried to find a situation where running the algorithm with no modifications would give the correct results, despite there is a negative weight somewhere. – danbanica Apr 22 '16 at 14:04
0

Example would be any graph, where negative edges leads to verticle with no edges beginning in it.

alxio
  • 128
  • 4