1
$\begingroup$

Recap to the Johnson's shortest path algorithm:

By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in V\}$, and then extend the original weighting function $\forall x \in V,\ w(s, x) = 0.$

Finally define the reweighted function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ where $\forall x \in V,\ h(x) = d(s, x)$ , where $d(s, x)$ is the shortest path from $s$ to $x$.

Problem:

Assume that there is no negative cycle in the graph. The textbook Introduction to Algorithms says that $w(u, v) + h(u) - h(v)$ is always nonnegative proven by using the triangular inequality theorem to get $w(u, v) + h(u) \ge h(v)$.

This makes me so confused, because I think that there could exist negative weights in the graph and hence triangular inequality can't be applied. (Am I misunderstanding triangular inequality? Or something are skipped I cannot tell?).

Where did I misunderstand about this algorithm? Thanks!

$\endgroup$
2
$\begingroup$

You're right that you can't (necessarily) apply the triangle inequality to the edges of the original graph, but that's not what's being discussed here.

We know $h(u)$ is, by definition, the shortest path to $u$. Thus we immediately know that $w(u,v) + h(u) \geq h(v)$ because, if it wasn't true, $h(v)$ would not be the shortest path to $v$. The author is calling this the "triangle inequality" of the reweighted graph.

$\endgroup$
  • $\begingroup$ Do you mean because $h(v)$ is the shortest distance from $s$ to $v$, and $w(u, v) + h(u)$ forms the distance of another path from $s$ to $v$ thus the inequality must hold? $\endgroup$ – OOD Waterball Jan 26 at 2:51
  • $\begingroup$ @OODWaterball: Yes, exactly $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 26 at 4:37

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.