# Proof showing when Dijkstra’s algorithm fails for negative edge weights

How do I show the correctness proof of Dijkstra’s algorithm for negative edge weight $$\textbf{indicating the point in the proof where it breaks or does not hold}?$$

I tried proving it like this, but i know that i'm not correct.

1. Set $$d[s] = 0$$ (where $$s$$ is our source).
2. Set $$d[v] = \infty$$ for all $$v \ne s$$,$$v \in V$$.
3. Run some sequence of UPDATE$$(u,v)$$ procedures on the edges of $$E$$.

Let $$SP(s,v)$$ denote the length of the shortest path from $$s$$ to vertex $$v$$. If we execute steps 1, 2, and 3, then $$d[v] \ge SP(s,v)$$ at the end of the process (no matter what sequence we specify in step 3).

To argue why this claim is true, we will use a very similar strategy we used in the proof of correctness: Assume, for sake of contradiction, that $$f$$ is the first vertex to violate this property, i.e., at some point during the procedure $$d[f] < SP(s, f)$$. Thus, there must have been some vertex $$u$$ such that we called UPDATE$$(u, f)$$, which resulted in $$d[u] + w(u, f)$$ being stored at $$d[f]$$ so that now $$d[f] < SP(s, f)$$. But $$f$$ is the first violator of this property, and so it must be the case that $$d[u] \ge SP(s,u)$$ when this update is called. Combining these observations it follows that

$$d[f] = d[u]+ w(u,v) \quad \text{(since u caused the violating update)}$$

$$\ge SP(s,u)+ w(u, f) \quad \text{(since f is the first violator;}\quad d[u] \ge SP(s,u))$$

$$\ge SP(s, f).$$

To see why the last inequality is true, note that the shortest path from $$s$$ to $$f$$ has to travel through one of $$f’s$$ neighboring vertices (i.e., any vertex $$v$$ such that $$(v, f) \in E)$$. $$u$$ is a candidate for this vertex, and if it is the case that we travel through $$u$$ on the shortest path from $$s$$ to $$f$$, then the length of this path is exactly $$SP(s,u)+ w(u, f)$$. The only other case would be if there is some better path that uses a vertex other than $$u$$, but in this case we have that $$SP(s, f) < SP(s,u)+w(u, f)$$, which proves the inequality.

Thus the last inequality show that $$d[f] \ge SP(s, f)$$, which contradicts the conditions we put on $$f$$ and therefore establishes our claim.

• You write $d[f] = d[u] + w(u, v)$. What is $v$? Nov 24, 2022 at 19:38

The proof is correct (modulo the typo I mentionned in the comment).

Why is that not a problem about Dijkstra's correctness for negative weights? Because what you proved is $$d[f] \geqslant SP(s, f)$$, not $$d[f] = SP(s, f)$$.

It is the inequality $$SP(s, f)\geqslant d[f]$$ at the end of the algorithm that fails with negative weights.

With the idea, I approached it as thus: An example below is used to show why Dijkstra's algorithm doesn't work in this case. The figure describes a directed graph that shows why Dijkstra’s algorithm does not work when the graph contains negative edges.

$$\textbf{N.B:}$$ The shaded vertices represent vertices that have been removed (dequeued) from the heap.\ In the proof of Dijkstra’s algorithm, the key property is that when a vertex $$v$$ is dequeued from the heap, its $$d[v]$$ value correctly stores the length of the shortest path from $$s$$ to $$v$$. Observe that in this example given in the graph, both $$u$$ and $$w$$ are violating this property, because both of these vertices have been removed from the heap, but we can attain shorter paths for both vertices by first travelling to $$v$$ and then taking the negative edge $$(v,u)$$. Even if we updated $$d[u]$$ to now be $$1$$ after dequeuing $$v$$ and calling UPDATE, $$d[w]$$ would still be incorrect.

$$\textbf{Proof of failure with negative weights:}$$ From lecture note 17 - "$$\emph{Graph Algorithms}$$", we could see that since both $$y$$ and $$u$$ were in $$S$$ when $$u$$ was chosen, so $$f[u] \le f[y]$$.

The two inequalities $$f(u) > d(s, u) \ge d(s, y)$$ became equalities, $$f[y] = d(s,y) = d(s,u) = f[u]$$; So $$f[u] = d(s,u)$$ contradicts our hypothesis. Thus when each $$u$$ was inserted, $$f[u] = d(s,u)$$.

Hence the inequality $$f(u) > d(s, u) \ge d(s, y)$$ fails if there is a negative weight because with negative weight introduced to the graph, $$d(s, u)$$ will not always be greater than $$d(s, y)$$, so Dijkstra’s algorithm fails here. Based on the proof by contradiction, there must be at least one more edge in the path after $$y$$, and the shortest path from $$s$$ to $$y$$ must be strictly smaller than the shortest path from $$s$$ to $$u$$. But with negative edge weight, this fails. So the inequality makes this contradiction invalid. QED

[Image Credit: ece.mcmaster.ca]