Updating the distances matrix after single edge was decreased

I was reading this question on how to update the distances matrix D of a graph after one edge was decreased, and I don't understand why it works:

The answer suggests that if the an edge (a,b) was modified - then all you have to do is iterate through every edge of the graph, and calculate: D[u][a] + w(a,b) + D[b][v].

My problem is: how do you know that D[u][a] is correct ?

I've drawn this example:

Now D[u][a] = 100
but, when the edge from a to b decreases:

Now D[u][a] should to be changed to 71 but it's not. and when I will calculate D[u][v] I would use a false D[u][a].

What am I missing here ? is the algorithm presented in the answer linked not correct ? or am I ?

Let me start with the setup, for the simpler case of a directed graph. We are given a weighted directed graph $G$ (with non-negative weights), and for every two vertices $s,t$, the distance $\delta(s,t)$ of a shortest directed path from $s$ to $t$. We modify $G$ to a new graph $G'$ by reducing the weight of an edge $(a,b)$, from $w(a,b)$ to $w'(a,b)$. The claim is that
$$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t)). $$
(In fact, the claim we want to prove is a bit stronger, since presumably we will be updating the metric sequentially rather than in parallel, but let's leave that for the future.)

In order to prove this formula, we consider two cases.

Case 1. Suppose first that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which doesn't go through the edge $(a,b)$. I claim that $p'$ is also a shortest path from $s$ to $t$ in $G$, and so $\delta'(s,t) = \delta(s,t)$. If not, let $p$ be a shorter path from $s$ to $t$ in $G$. Then $w_{G'}(p) \leq w_G(p) < w_G(p') = w_{G'}(p')$, contradicting the definition of $p'$.

It remains to show that $\delta(s,t) \leq \delta(s,a) + w'(a,b) + \delta(b,t)$. Suppose not, and take shortest paths $p_{sa}$ from $s$ to $a$ and $p_{bt}$ from $b$ to $t$, both in $G$. Let $p$ be the (not necessarily simple) path $p_{sa};(a,b);p_{bt}$, so that $w_{G'}(p) = \delta(s,a) + w'(a,b) + \delta(b,t)$. Since $w_{G'}(p) < \delta(s,t) = w_{G'}(p')$, this implies that $p'$ is not a shortest path in $G'$, contradicting its definition.

Case 2. Suppose next that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which goes through the edge $(a,b)$, say $p' = p'_{sa};(a,b);p'_{bt}$. Since $p'$ is a shortest path and all weights are non-negative, we can assume without loss of generality that $p'$ is simple, and so $p'_{sa},p'_{bt}$ don't go through $(a,b)$.

We claim that $p'_{sa}$ is a shortest path from $s$ to $a$ in $G$, and so has length $\delta(s,a)$. If not, let $p_{sa}$ be a shorter path from $s$ to $a$ in $G$. Without loss of generality, $p_{sa}$ doesn't go through $(a,b)$, since if it did, we would have $p_{sa} = q;(a,b);r$, and could replace $p_{sa}$ with $q$. Since $p_{sa}$ doesn't go through $(a,b)$, it has the same weight in $G$ and in $G'$, and so if we replace $p'_{sa}$ with $p_{sa}$, we would shorten $p'$ in $G'$, contradicting its definition. Similarly, $p'_{bt}$ is a shortest path from $b$ to $t$ in $G$, and so has length $\delta(b,t)$. We conclude that $\delta'(s,t) = \delta(s,a) + w'(a,b) + \delta(b,t)$.

It remains to show that $\delta(s,a) + w'(a,b) + \delta(b,t) \leq \delta(s,t)$. If not, let $p$ be a shortest path from $s$ to $t$ in $G$. Then $w_{G'}(p) \leq w_G(p) = \delta(s,t) < w_{G'}(p')$, contradicting the fact that $p'$ is a shortest path in $G'$.

In the undirected case, we are lowering the weights of two edges, and so the correct formula is
$$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t), \delta(s,b) + w'(b,a) + \delta(a,t). $$
(Note $w'(b,a) = w'(a,b)$.)

StackExchange Computer Science Q#76846, answer score: 5