Updating the distances matrix after single edge was decreased
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) &lt; 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) &lt; \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) &lt; 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)$.)