5
$\begingroup$

I was reading on 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: enter image description here

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

enter image description here

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 to isn't correct ? or am I ?

$\endgroup$
  • 1
    $\begingroup$ If it's indeed incorrect, it won't be the first time an algorithm on stackoverflow is incorrect... $\endgroup$ – Yuval Filmus Jun 15 '17 at 20:11
4
$\begingroup$

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)$.)

$\endgroup$
  • $\begingroup$ If there are any mistakes (especially in notation), please correct them. $\endgroup$ – Yuval Filmus Jun 15 '17 at 20:45
  • $\begingroup$ Small thing - is it required to create a new delta' instead of just updating the given delta with the result from the min operation ? or it doesn't matter ? $\endgroup$ – shaqed Jun 16 '17 at 10:02
  • 1
    $\begingroup$ It probably works even when updating $\delta$, but this requires additional proof (along very similar lines). I alluded to that in my comment "(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.)". $\endgroup$ – Yuval Filmus Jun 16 '17 at 11:07
  • $\begingroup$ When you use the updated matrix in place of the old one, you can only see shorter distances than you would have otherwise, and thus you cannot introduce longer distances than you would have otherwise. It's also easy to see that you can't get shorter distances as a result than you would have otherwise. It's the same exact reason as why you can do this trick in the Floyd-Warshall algorithm. $\endgroup$ – John Dvorak Oct 31 '18 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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