# How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?

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!

## 1 Answer

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.

• 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? – OOD Waterball Jan 26 at 2:51
• @OODWaterball: Yes, exactly – BlueRaja - Danny Pflughoeft Jan 26 at 4:37