# Ch24: Single-Source Shortest Paths
###### tags: `algorithm`
:::success
- contributed by < `TYChan6028` >
- textbook: [Introduction to Algorithms, Third Edition](https://mitpress.mit.edu/books/introduction-algorithms-third-edition)
:::
## Exercises 24.1
### *24.1-1* Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex $z$ as the source. In each pass, relax edges in the same order as in the figure, and show the $d$ and $\pi$ values after each pass. Now, change the weight of edge $(z,x)$ to 4 and run the algorithm again, using $s$ as the source.
Order of traverse: $z \rightarrow y \rightarrow s \rightarrow t \rightarrow x$
```graphviz
digraph row_1 {
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
subgraph cluster_1 {
label="Original"
labelloc="b"
color="transparent"
s [label="∞", xlabel="s"]
t [label="∞", xlabel="t"]
x [label="∞", xlabel="x"]
y [label="∞", xlabel="y"]
z [label=0, xlabel="z", fillcolor="#fbf8e5"]
s -> t [headlabel="6"]
s -> y [headlabel="7"]
t -> x [headlabel="5"]
t -> z [headlabel="-4"]
t -> y [headlabel="8"]
x -> t [headlabel="-2"]
y -> z [headlabel="9"]
y -> x [xlabel="-3"]
z -> s [xlabel="2"]
z -> x [headlabel="7"]
{rank=same;s t x}
{rank=same;y z}
}
subgraph cluster_2 {
label="Pass 1"
labelloc="b"
color="transparent"
s2 [label=2, xlabel="s"]
t2 [label=5, xlabel="t"]
x2 [label=7, xlabel="x"]
y2 [label=9, xlabel="y"]
z2 [label=0, xlabel="z", fillcolor="#fbf8e5"]
s2 -> t2 [headlabel="6"]
s2 -> y2 [headlabel="7", color=red]
t2 -> x2 [headlabel="5"]
t2 -> z2 [headlabel="-4"]
t2 -> y2 [headlabel="8"]
x2 -> t2 [headlabel="-2", color=red]
y2 -> z2 [headlabel="9"]
y2 -> x2 [xlabel="-3"]
z2 -> s2 [xlabel="2", color=red]
z2 -> x2 [headlabel="7", color=red]
{rank=same;s2 t2 x2}
{rank=same;y2 z2}
}
}
```
```graphviz
digraph row_2 {
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
subgraph cluster_3 {
label="Pass 2"
labelloc="b"
color="transparent"
s3 [label=2, xlabel="s"]
t3 [label=4, xlabel="t"]
x3 [label=6, xlabel="x"]
y3 [label=9, xlabel="y"]
z3 [label=0, xlabel="z", fillcolor="#fbf8e5"]
s3 -> t3 [headlabel="6"]
s3 -> y3 [headlabel="7", color=red]
t3 -> x3 [headlabel="5"]
t3 -> z3 [headlabel="-4"]
t3 -> y3 [headlabel="8"]
x3 -> t3 [headlabel="-2", color=red]
y3 -> z3 [headlabel="9"]
y3 -> x3 [xlabel="-3", color=red]
z3 -> s3 [xlabel="2", color=red]
z3 -> x3 [headlabel="7"]
{rank=same;s3 t3 x3}
{rank=same;y3 z3}
}
subgraph cluster_4 {
label="Pass 3"
labelloc="b"
color="transparent"
s4 [label=2, xlabel="s"]
t4 [label=4, xlabel="t"]
x4 [label=6, xlabel="x"]
y4 [label=9, xlabel="y"]
z4 [label=0, xlabel="z", fillcolor="#fbf8e5"]
s4 -> t4 [headlabel="6"]
s4 -> y4 [headlabel="7", color=red]
t4 -> x4 [headlabel="5"]
t4 -> z4 [headlabel="-4"]
t4 -> y4 [headlabel="8"]
x4 -> t4 [headlabel="-2", color=red]
y4 -> z4 [headlabel="9"]
y4 -> x4 [xlabel="-3", color=red]
z4 -> s4 [xlabel="2", color=red]
z4 -> x4 [headlabel="7"]
{rank=same;s4 t4 x4}
{rank=same;y4 z4}
}
}
```
```graphviz
digraph row_3 {
label="Pass 4 (final)"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
s5 [label=2, xlabel="s"]
t5 [label=4, xlabel="t"]
x5 [label=6, xlabel="x"]
y5 [label=9, xlabel="y"]
z5 [label=0, xlabel="z", fillcolor="#fbf8e5"]
s5 -> t5 [headlabel="6"]
s5 -> y5 [headlabel="7", color=red]
t5 -> x5 [headlabel="5"]
t5 -> z5 [headlabel="-4"]
t5 -> y5 [headlabel="8"]
x5 -> t5 [headlabel="-2", color=red]
y5 -> z5 [headlabel="9"]
y5 -> x5 [xlabel="-3", color=red]
z5 -> s5 [xlabel="2", color=red]
z5 -> x5 [headlabel="7"]
{rank=same;s5 t5 x5}
{rank=same;y5 z5}
}
```
The graph with $w(z,x)=4$ and $s$ as the source can be obtained by using the same process.
### *24.1-2* Prove Corollary 24.3.
> ***Corollary 24.3***
> Let $G=(V,E)$ be a weighted, directed graph with source vertex $s$ and weight function $w:E \rightarrow \mathbb{R}$, and assume that $G$ contains no negative-weight cycles that are reachable from s. Then, for each vertex $v \in V$, there is a path from $s$ to $v$ if and only if `BELLMAN-FORD` terminates with $v.d<\infty$ when it is run on $G$. -- <cite>textbook, p.653</cite>
#### *Proof*
We will prove this by contradiction.
Let graph $G$ be initialized with a call to `INITIALIZE- SINGLE-SOURCE`, which sets $s.d=0$ and $v.d=\infty$ for $v \in V-\{s\}$.
At `BELLMAN-FORD`'s termination, assume there exists a $v.d=\infty$ on the path $p=<v_0, v_1,..., v_k>$ from $s \rightsquigarrow v$, where $s=v_0$ and $v=v_k$. Since $v.d=\delta(s,v)$ for all $v \in V$ at termination,
$\begin{eqnarray}
v.d &=& \delta(s,v_k)\\
&=& \infty\\
&\leq& \delta(s,v_{k-1})+w(v_{k-1},v_k)\\
\end{eqnarray}$
We know $w(v_{k-1},v_k) \neq \infty$, so $\delta(s,v_{k-1})=\infty$. The same can be said for $\delta(s,v_{k-1})$ to $\delta(s,v_1)$, until
$\begin{eqnarray}
\delta(s,v_1) &=& \infty\\
&\leq& \delta(s,v_0)+w(s,v_1)\\
&=& \delta(s,s)+w(s,1)\\
\Longrightarrow \delta(s,s) &=& \infty
\end{eqnarray}$
This contradicts with $s.d=0$, which proves there is no path from $s$ to $v$ if `BELLMAN-FORD` terminates with $v.d=\infty$.
## Exercises 24.2
### *24.2-1* Run `DAG-SHORTEST-PATHS` on the directed graph of Figure 24.5, using vertex $r$ as the source.
```graphviz
digraph dag {
label="Original"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label="∞", xlabel="s"]
t [label="∞", xlabel="t"]
x [label="∞", xlabel="x"]
y [label="∞", xlabel="y"]
z [label="∞", xlabel="z"]
r -> s [xlabel="5"]
s -> t [xlabel="2"]
t -> x [xlabel="7"]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3"]
s -> x [xlabel="6"]
x -> z [xlabel="1"]
t:s -> y [xlabel="4"]
t:s -> z [xlabel="2"]
{rank=same;r s t x y z}
}
```
```graphviz
digraph dag {
label="Explore r"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label=5, xlabel="s"]
t [label=3, xlabel="t"]
x [label="∞", xlabel="x"]
y [label="∞", xlabel="y"]
z [label="∞", xlabel="z"]
r -> s [xlabel="5", color=red]
s -> t [xlabel="2"]
t -> x [xlabel="7"]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3", color=red]
s -> x [xlabel="6"]
x -> z [xlabel="1"]
t:s -> y [xlabel="4"]
t:s -> z [xlabel="2"]
{rank=same;r s t x y z}
}
```
```graphviz
digraph dag {
label="Explore s"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label=5, xlabel="s"]
t [label=3, xlabel="t"]
x [label=11, xlabel="x"]
y [label="∞", xlabel="y"]
z [label="∞", xlabel="z"]
r -> s [xlabel="5", color=red]
s -> t [xlabel="2"]
t -> x [xlabel="7"]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3", color=red]
s -> x [xlabel="6", color=red]
x -> z [xlabel="1"]
t:s -> y [xlabel="4"]
t:s -> z [xlabel="2"]
{rank=same;r s t x y z}
}
```
```graphviz
digraph dag {
label="Explore t"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label=5, xlabel="s"]
t [label=3, xlabel="t"]
x [label=10, xlabel="x"]
y [label=7, xlabel="y"]
z [label=5, xlabel="z"]
r -> s [xlabel="5", color=red]
s -> t [xlabel="2"]
t -> x [xlabel="7", color=red]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3", color=red]
s -> x [xlabel="6"]
x -> z [xlabel="1"]
t:s -> y [xlabel="4", color=red]
t:s -> z [xlabel="2", color=red]
{rank=same;r s t x y z}
}
```
```graphviz
digraph dag {
label="Explore x"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label=5, xlabel="s"]
t [label=3, xlabel="t"]
x [label=10, xlabel="x"]
y [label=7, xlabel="y"]
z [label=5, xlabel="z"]
r -> s [xlabel="5", color=red]
s -> t [xlabel="2"]
t -> x [xlabel="7", color=red]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3", color=red]
s -> x [xlabel="6"]
x -> z [xlabel="1"]
t:s -> y [xlabel="4", color=red]
t:s -> z [xlabel="2", color=red]
{rank=same;r s t x y z}
}
```
```graphviz
digraph dag {
label="Explore y"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label=5, xlabel="s"]
t [label=3, xlabel="t"]
x [label=10, xlabel="x"]
y [label=7, xlabel="y"]
z [label=5, xlabel="z"]
r -> s [xlabel="5", color=red]
s -> t [xlabel="2"]
t -> x [xlabel="7", color=red]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3", color=red]
s -> x [xlabel="6"]
x -> z [xlabel="1"]
t:s -> y [xlabel="4", color=red]
t:s -> z [xlabel="2", color=red]
{rank=same;r s t x y z}
}
```
```graphviz
digraph dag {
label="Explore z (final)"
labelloc="b"
color="transparent"
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
r [label=0, xlabel="r", fillcolor="#fbf8e5"]
s [label=5, xlabel="s"]
t [label=3, xlabel="t"]
x [label=10, xlabel="x"]
y [label=7, xlabel="y"]
z [label=5, xlabel="z"]
r -> s [xlabel="5", color=red]
s -> t [xlabel="2"]
t -> x [xlabel="7", color=red]
x -> y [xlabel="-1"]
y -> z [xlabel="-2"]
r:s -> t [xlabel="3", color=red]
s -> x [xlabel="6"]
x -> z [xlabel="1"]
t:s -> y [xlabel="4", color=red]
t:s -> z [xlabel="2", color=red]
{rank=same;r s t x y z}
}
```
### *24.2-2* Suppose we change line 3 of `DAG-SHORTEST-PATHS` to read `for the first |V| - 1 vertices, taken in topologically sorted order`. Show that the procedure would remain correct.
```javascript
DAG-SHORTEST-PATHS(G,w,s)
```
```javascript=
topologically sort the vertices of G
INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex u, taken in topologically sorted order
for each vertex v in G.Adj[u]
RELAX(u,v,w)
```
#### *Proof*
Let topologically-sorted $V=<v_1,v_2,...,v_k>$, then $v_k$ has no child nodes. This shows that there does not exist a $v_{k+1}$ for which $\delta(s,v_{k+1}) \leq \delta(s,v_k)+w(v_k,v_{k+1})$ could relax. Since `G.Adj[u]`$=\emptyset$, the `for` loop on line `4` would go through 0 iterations. Therefore, it is safe to only consider the first $|V|-1$ vertices.
## Exercises 24.3
### *24.3-1* Run Dijkstra’s algorithm on the directed graph of Figure 24.2, first using vertex $s$ as the source and then using vertex $z$ as the source. In the style of Figure 24.6, show the $d$ and $\pi$ values and the vertices in set $S$ after each iteration of the `while` loop.
```graphviz
digraph row_1 {
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
subgraph cluster_1 {
label="Original"
labelloc="b"
color="transparent"
s [label=0, xlabel="s", fillcolor="#fbf8e5"]
t [label="∞", xlabel="t"]
x [label="∞", xlabel="x"]
y [label="∞", xlabel="y"]
z [label="∞", xlabel="z"]
s -> t [xlabel="3"]
s -> y [xlabel="5"]
t -> x [xlabel="6"]
t -> y [xlabel="2"]
x -> z [xlabel="2"]
y -> t [xlabel="1"]
y -> x [xlabel="4"]
y -> z [xlabel="6"]
z -> s [xlabel="3"]
z -> x [xlabel="7"]
{rank=same;t y}
{rank=same;x z}
}
subgraph cluster_2 {
label="S = {s}"
labelloc="b"
color="transparent"
s2 [label=0, xlabel="s", fillcolor="#fbf8e5"]
t2 [label=3, xlabel="t"]
x2 [label="∞", xlabel="x"]
y2 [label=5, xlabel="y"]
z2 [label="∞", xlabel="z"]
s2 -> t2 [xlabel="3", color=red]
s2 -> y2 [xlabel="5", color=red]
t2 -> x2 [xlabel="6"]
t2 -> y2 [xlabel="2"]
x2 -> z2 [xlabel="2"]
y2 -> t2 [xlabel="1"]
y2 -> x2 [xlabel="4"]
y2 -> z2 [xlabel="6"]
z2 -> s2 [xlabel="3"]
z2 -> x2 [xlabel="7"]
{rank=same;t2 y2}
{rank=same;x2 z2}
}
}
```
```graphviz
digraph row_2 {
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
subgraph cluster_3 {
label="S = {s, t}"
labelloc="b"
color="transparent"
s3 [label=0, xlabel="s", fillcolor="#fbf8e5"]
t3 [label=3, xlabel="t"]
x3 [label=9, xlabel="x"]
y3 [label=5, xlabel="y"]
z3 [label="∞", xlabel="z"]
s3 -> t3 [xlabel="3", color=red]
s3 -> y3 [xlabel="5", color=red]
t3 -> x3 [xlabel="6", color=red]
t3 -> y3 [xlabel="2"]
x3 -> z3 [xlabel="2"]
y3 -> t3 [xlabel="1"]
y3 -> x3 [xlabel="4"]
y3 -> z3 [xlabel="6"]
z3 -> s3 [xlabel="3"]
z3 -> x3 [xlabel="7"]
{rank=same;t3 y3}
{rank=same;x3 z3}
}
subgraph cluster_4 {
label="S = {s, t, y}"
labelloc="b"
color="transparent"
s4 [label=0, xlabel="s", fillcolor="#fbf8e5"]
t4 [label=3, xlabel="t"]
x4 [label=9, xlabel="x"]
y4 [label=5, xlabel="y"]
z4 [label=11, xlabel="z"]
s4 -> t4 [xlabel="3", color=red]
s4 -> y4 [xlabel="5", color=red]
t4 -> x4 [xlabel="6", color=red]
t4 -> y4 [xlabel="2"]
x4 -> z4 [xlabel="2"]
y4 -> t4 [xlabel="1"]
y4 -> x4 [xlabel="4"]
y4 -> z4 [xlabel="6", color=red]
z4 -> s4 [xlabel="3"]
z4 -> x4 [xlabel="7"]
{rank=same;t4 y4}
{rank=same;x4 z4}
}
}
```
```graphviz
digraph row_3 {
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
subgraph cluster_5 {
label="S = {s, t, y, x}"
labelloc="b"
color="transparent"
s5 [label=0, xlabel="s", fillcolor="#fbf8e5"]
t5 [label=3, xlabel="t"]
x5 [label=9, xlabel="x"]
y5 [label=5, xlabel="y"]
z5 [label=11, xlabel="z"]
s5 -> t5 [xlabel="3", color=red]
s5 -> y5 [xlabel="5", color=red]
t5 -> x5 [xlabel="6", color=red]
t5 -> y5 [xlabel="2"]
x5 -> z5 [xlabel="2"]
y5 -> t5 [xlabel="1"]
y5 -> x5 [xlabel="4"]
y5 -> z5 [xlabel="6", color=red]
z5 -> s5 [xlabel="3"]
z5 -> x5 [xlabel="7"]
{rank=same;t5 y5}
{rank=same;x5 z5}
}
subgraph cluster_6 {
label="S = {s, t, y, x, z} (final)"
labelloc="b"
color="transparent"
s6 [label=0, xlabel="s", fillcolor="#fbf8e5"]
t6 [label=3, xlabel="t"]
x6 [label=9, xlabel="x"]
y6 [label=5, xlabel="y"]
z6 [label=11, xlabel="z"]
s6 -> t6 [xlabel="3", color=red]
s6 -> y6 [xlabel="5", color=red]
t6 -> x6 [xlabel="6", color=red]
t6 -> y6 [xlabel="2"]
x6 -> z6 [xlabel="2"]
y6 -> t6 [xlabel="1"]
y6 -> x6 [xlabel="4"]
y6 -> z6 [xlabel="6", color=red]
z6 -> s6 [xlabel="3"]
z6 -> x6 [xlabel="7"]
{rank=same;t6 y6}
{rank=same;x6 z6}
}
}
```
The graph with vertex $z$ as the source can be obtained by using the same process.
### *24.3-2* Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s algorithm produces incorrect answers. Why doesn’t the proof of Theorem 24.6 go through when negative-weight edges are allowed?
```javascript
DIJKSTRA(G,w,s)
```
```javascript=
INITIALIZE-SINGLE-SOURCE(G,s)
S = empty set
Q = G.V
while Q != empty set
u = EXTRACT-MIN(Q)
S = UNION(S,{u})
for each vertex v in G.Adj[u]
RELAX(u,v,w)
```
Below is an example for which Dijkstra's algorithm produces an incorrect answer. The negative-weight edge $u \rightarrow z$ creates a negative cycle $y \rightarrow u \rightarrow z \rightarrow y$ for which an even smaller weight can always be achieved by traversing the cycle indefinitely.
```graphviz
digraph row_3 {
forcelabels=true
node [shape="circle", style=filled, fillcolor=transparent]
edge [color="#78a0bf", fontcolor=navy, len=2]
nodesep=1.5
label="S = {s, x, t, (y, u, z = negative cycle)}"
labelloc="b"
color="transparent"
s6 [label=0, xlabel="s", fillcolor="#fbf8e5"]
x6 [label=3, xlabel="x"]
y6 [label=8, xlabel="y", fillcolor="#efdfde"]
t6 [label=5, xlabel="t"]
z6 [label=1, xlabel="z", fillcolor="#efdfde"]
u6 [label=10, xlabel="u", fillcolor="#efdfde"]
s6 -> x6 [xlabel="3", color=red]
s6 -> t6 [xlabel="5", color=red]
x6 -> y6 [xlabel="6", color=red]
x6 -> t6 [xlabel="2"]
y6 -> z6 [xlabel="2"]
y6 -> u6 [xlabel="1", color=red]
t6 -> x6 [xlabel="1"]
t6 -> y6 [xlabel="4"]
t6 -> z6 [xlabel="6"]
z6 -> s6 [xlabel="3"]
z6 -> y6 [xlabel="7", color=red]
u6 -> z6 [xlabel="-9", color=red]
{rank=same;s6 t6 z6}
{rank=same;x6 y6 u6}
}
```
> ***Theorem 24.6 (Correctness of Dijkstra’s algorithm)***
> Dijkstra’s algorithm, run on a weighted, directed graph $G=(V,E)$ with non-negative weight function $w$ and source $s$, terminates with $u.d=\delta(s,u)$ for all vertices $u \in V$.
Theorem 24.6 proves correctness by showing, for each vertex $u \in V$, $u.d=\delta(s,u)$ at the time when $u$ is added to set $S$. Once the equality is shown, it relies on the upper-bound property to uphold the equality at all times thereafter. Therefore, the algorithm would terminate with $u.d=\delta(s,u)$ for all vertices $u \in S=V$.
The proof of Theorem 24.6 illustrates a shortest path from $s \overset{p_1}{\rightsquigarrow} x \rightarrow y \overset{p_2}{\rightsquigarrow} u$, on which $s,x \in S$ and $y,u \in V-S$. It makes a claim that $u$ is the first vertex for which $u.d \neq \delta(s,u)$ when it is added to $S$, then attempts to disprove this by contradiction.
By proving $y.d=\delta(s,y)$ and because all edge weights are non-negative, it arrives at the relations
\begin{eqnarray}
y.d &=& \delta(s,y)\\
&\leq& \delta(s,u)\\
&\leq& u.d
\end{eqnarray}
Since $y,u \in V-S$ and $u$ is chosen over $y$ to be next included in set $S$, $u.d \leq y.d$. Combined with the relation shown above, $y.d=\delta(s,y)=\delta(s,u)=u.d$, which contradicts its claim and completes the proof.
The reason why the proof of Theorem 24.6 does not go through when negative-weight edges are allowed is because we can no longer make the assumption that $\delta(s,y) \leq \delta(s,u)$.
We know $y.d=\delta(s,y) \geq u.d$, but if $\delta(s,y)>\delta(s,u)$ due to a negative-weight edge, it is possible that
1. $y.d=\delta(s,y)=u.d>\delta(s,u)$
2. $\delta(s,y)>u.d=a$ and $\delta(s,y)>\delta(s,u)=b$ for which $a \neq b$
Sign in with Wallet
Connect another wallet