Dijkstra's Algorithm for Negative Weights.

Question

Now the problem states that their is a graph $ G = (V,E) $ where some of the edges have negative weights while some of the edges have positive edges. Now the question is why won't Dijkstra's algorithm work if we add the most negative weight + 1 to every edge. (Example: The most negative weight in the graph of an edge is -100 so we add 101 to every edge.)

Now I know the reason behind why it won't work. Path with more edges will be favoured (They will have the most increase in their weights hence Dijkstra won't work here).

Now the problem I'm having is that they want me to prove this. Following I've attempted the proof. I just want to check if I'm doing it correctly or not?

Attempted Proof:

Let us assume there is a graph $G = (V,E)$ and we pick two paths $s....x$ and $s....y$ and this graph contains some edges with negative weights.

$d(x) = w(s,a) + w(a,b) + w(b,c) + ....... + w(v,x) $ $d(x) = w(s,e) + w(e,f) + w(f,g) + ....... + w(u,y) $

where $d(x)$ is the total weights of the path $s....x$ and $w(a,b)$ is the weight of the edge $a - b$

Now when we add a certain amount to both the paths:

$d(x) = w(s,a) + w(a,b) + w(b,c) + ....... + w(v,x) + Amount * Edges_X $ $d(x) = w(s,e) + w(e,f) + w(f,g) + ....... + w(u,y) + Amount * Edges_Y $

Now the path which contain more edges will have more amount being added to it and this is the reason Dijkstra will not work.

Answer 1

Always be aware of the logical structure of what you want to prove. The theorem that Dijkstra works for arbitrary weighted graphs is of the form:

For any weighted graph $G$ and source $S$ and destination $T$, Dijkstra finds some shortest path from $S$ to $T$ in $G$.

Thus if you want to prove that Dijkstra does not work, you want to prove the negation is true. The negation is:

For some weighted graph $G$ and source $S$ and destination $T$, Dijkstra does not find any shortest path from $S$ to $T$ in $G$.

Note that an often overlooked fact is that Dijkstra does not necessarily find the shortest path you may have in mind, since there may be more than one.