algorithmgraph-theoryshortest-pathdijkstragreedy

Why doesn't Dijkstra's algorithm work for negative weight edges?

Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative.

I am talking about only edges not the negative weight cycles.

Solution

  • Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

    But with negative weights - it might not be true. For example:

           A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

    Dijkstra from A will first develop C, and will later fail to find A->B->C

    EDIT a bit deeper explanation:

    Note that this is important, because in each relaxation step, the algorithm assumes the "cost" to the "closed" nodes is indeed minimal, and thus the node that will next be selected is also minimal.

    The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
    Without the constraint on positive numbers - the above assumption is not true.

    Since we do "know" each vertex which was "closed" is minimal - we can safely do the relaxation step - without "looking back". If we do need to "look back" - Bellman-Ford offers a recursive-like (DP) solution of doing so.