Search code examples
algorithmdijkstra

Dijkstra Algorithm = SSSP

enter image description here

What i have learnt , that dijkstra cannot work with negative edge weights . For that we have to use bellman ford .

Bellman fords works well with negative edge weights and negative cycles , which are not reachable from source otherwise, it will return a msg "Negative cycles exist".

But, this graph shown above works well with dijkstra , even though negative edge weights exist. So, how to know when to use dijkstra with negative edge weights ??

What is think , is that dijkstra can or cannot work with negative weight edges. If negative cycle exists, then it will not work. But if not exists, it can or cannot work.

Am i right ?? plz guide me for this ??

Solution

  • Dijkstra's algorithm cannot work with negative edge weights. This is because once it marks a node as "visited", it assumes the shortest path to it has been found, and can not change, an invariant easily violated in graphs with negative edges (and no negative cycles):

           A
      / \
    7/   \2
    /     \
   B------>C
      -6

    Finding shortest paths with Dijkstra's algorithm starting from A will produce the wrong cost for C, 2.

    The graph you posted doesn't work either: consider the shortest path starting from d to h. Dijkstra's on this graph will produce 4 for the path (d->g->h), whereas there's a cheaper path of 0 cost: d->a->b->c->h