Negative weights using Dijkstra s Algorithm

Question

I am trying to understand why Dijkstra s algorithm will not work with negative weights  Reading an example on Shortest Paths  I am trying to figure out the following scenario       2 A-------B          3       -2            C   From the website      Assuming the edges are all directed from left to right  If we start   with A  Dijkstra s algorithm will choose the edge  A x  minimizing   d A A  length edge   namely  A B   It then sets d A B  2 and chooses   another edge  y C  minimizing d A y  d y C   the only choice is  A C    and it sets d A C  3  But it never finds the shortest path from A to   B  via C  with total length 1    I can not understand why using the following implementation of Dijkstra  d B  will not be updated to 1  When the algorithm reaches vertex C  it will run a relax on B  see that the d B  equals to 2  and therefore update its value to 1    Dijkstra G  w  s        Initialize-Single-Source G  s     S         Q   V G   priority queue by d v     while Q      do       u   Extract-Min Q        S   S U  u        for each vertex v in Adj u  do          Relax u  v     Initialize-Single-Source G  s       for each vertex v   V G        d v    8       p v    NIL    d s    0    Relax u  v         update only if we found a strictly shortest path    if d v   gt  d u    w u v         d v    d u    w u v        p v    u       Update Q  v      Thanks   Meir

User · Answer

Since Dijkstra is a Greedy approach  once a vertice is marked as visited for this loop  it would never be reevaluated again even if there s another path with less cost to reach it later on  And such issue could only happen when negative edges exist in the graph      A greedy algorithm  as the name suggests  always makes the choice that seems to be the best at that moment  Assume that you have an objective function that needs to be optimized  either maximized or minimized  at a given point  A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized  The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision

User · Answer

2  Can we use Dijksra   s algorithm for shortest paths for graphs with negative weights     one idea can be  calculate the minimum weight value  add a positive value  equal to absolute value of minimum weight value  to all weights and run the Dijksra   s algorithm for the modified graph  Will this algorithm work    This absolutely doesn t work unless all shortest paths have same length  For example given a shortest path of length two edges  and after adding absolute value to each edge  then the total path cost is increased by 2    max negative weight   On the other hand another path of length three edges  so the path cost is increased by 3    max negative weight   Hence  all distinct paths are increased by different amounts

User · Answer

The algorithm you have suggested will indeed find the shortest path in this graph  but not all graphs in general  For example  consider this graph   Let s trace through the execution of your algorithm   First  you set d A  to 0 and the other distances to 8  You then expand out node A  setting d B  to 1  d C  to 0  and d D  to 99  Next  you expand out C  with no net changes  You then expand out B  which has no effect  Finally  you expand D  which changes d B  to -201   Notice that at the end of this  though  that d C  is still 0  even though the shortest path to C has length -200  This means that your algorithm doesn t compute the correct distances to all the nodes  Moreover  even if you were to store back pointers saying how to get from each node to the start node A  you d end taking the wrong path back from C to A  The reason for this is that Dijkstra s algorithm  and your algorithm  are greedy algorithms that assume that once they ve computed the distance to some node  the distance found must be the optimal distance  In other words  the algorithm doesn t allow itself to take the distance of a node it has expanded and change what that distance is  In the case of negative edges  your algorithm  and Dijkstra s algorithm  can be  quot surprised quot  by seeing a negative-cost edge that would indeed decrease the cost of the best path from the starting node to some other node  Hope this helps

User · Answer

you did not use S anywhere in your algorithm  besides modifying it   the idea of dijkstra is once a vertex is on S  it will not be modified ever again  in this case  once B is inside S  you will not reach it again via C   this fact ensures the complexity of O E VlogV   otherwise  you will repeat edges more then once  and vertices more then once   in other words  the algorithm you posted  might not be in O E VlogV   as promised by dijkstra s algorithm

User · Answer

You can use dijkstra s algorithm with negative edges not including negative cycle  but you must allow a vertex can be visited multiple times and that version will lose it s fast time complexity    In that case practically I ve seen it s better to use SPFA algorithm which have normal queue and can handle negative edges

User · Answer

Consider what happens if you go back and forth between B and C   voila   relevant only if the graph is not directed   Edited   I believe the problem has to do with the fact that the path with AC  can only be better than AB with the existence of negative weight edges  so it doesn t matter where you go after AC  with the assumption of non-negative weight edges it is impossible to find a path better than AB once you chose to reach B after going AC

User · Answer

TL DR  The answer depends on your implementation  For the pseudo code you posted  it works with negative weights   Variants of Dijkstra s Algorithm The key is there are 3 kinds of implementation of Dijkstra s algorithm  but all the answers under this question ignore the differences among these variants   Using a nested for-loop to relax vertices  This is the easiest way to implement Dijkstra s algorithm  The time complexity is O V 2   Priority-queue heap based implementation   NO re-entrance allowed  where re-entrance means a relaxed vertex can be pushed into the priority-queue again to be relaxed again later  Priority-queue heap based implementation   re-entrance allowed   Version 1  amp  2 will fail on graphs with negative weights  if you get the correct answer in such cases  it is just a coincidence   but version 3 still works  The pseudo code posted under the original problem is the version 3 above  so it works with negative weights  Here is a good reference from Algorithm  4th edition   which says  and contains the java implementation of version 2  amp  3 I mentioned above    Q  Does Dijkstra s algorithm work with negative weights  A  Yes and no  There are two shortest paths algorithms known as Dijkstra s algorithm  depending on whether a vertex can be enqueued on the priority queue more than once  When the weights are nonnegative  the two versions coincide  as no vertex will be enqueued more than once   The version implemented in DijkstraSP java  which allows a vertex to be enqueued more than once  is correct in the presence of negative edge weights  but no negative cycles  but its running time is exponential in the worst case   We note that DijkstraSP java throws an exception if the edge-weighted digraph has an edge with a negative weight  so that a programmer is not surprised by this exponential behavior   If we modify DijkstraSP java so that a vertex cannot be enqueued more than once  e g   using a marked   array to mark those vertices that have been relaxed   then the algorithm is guaranteed to run in E log V time but it may yield incorrect results when there are edges with negative weights    For more implementation details and the connection of version 3 with Bellman-Ford algorithm  please see this answer from zhihu  It is also my answer  but in Chinese   Currently I don t have time to translate it into English  I really appreciate it if someone could do this and edit this answer on stackoverflow

User · Answer

Note  that Dijkstra works even for negative weights  if the Graph has no negative cycles  i e  cycles whose summed up weight is less than zero    Of course one might ask  why in the example made by templatetypedef Dijkstra fails even though there are no negative cycles  infact not even cycles  That is because he is using another stop criterion  that holds the algorithm as soon as the target node is reached  or all nodes have been settled once  he did not specify that exactly   In a graph without negative weights this works fine   If one is using the alternative stop criterion  which stops the algorithm when the priority-queue  heap  runs empty  this stop criterion was also used in the question   then dijkstra will find the correct distance even for graphs with negative weights but without negative cycles    However  in this case  the asymptotic time bound of dijkstra for graphs without negative cycles is lost  This is because a previously settled node can be reinserted into the heap when a better distance is found due to negative weights  This property is called label correcting

[algorithm] Negative weights using Dijkstra's Algorithm

Examples related to algorithm

Examples related to dijkstra

Examples related to shortest-path

Examples related to graph-algorithm