Graph theory -Problems and discussion


Why Dijkstras cant be used for graphs with negative weights?Also can BFS be used to find shortest path for a graph whose edge lengths are same ,positive or negative?


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:

  / \
 /   \
/     \
5       2
/           \

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

It 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.