0
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

enter image description here

$\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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.