Edge relaxations

Dependencies:

1. Triangle inequality of shortest paths

Let $G=(V,E)$ be a weighted graph. Also assume that $(u,v)\in E⟹w(u,v)\ne \mathrm{\infty }$. Let $s$ be a source vertex from which we wish to find the shortest path to every vertex. Let $\delta (v)$ be the weight of the shortest path from $s$ to $v$.

Let $d:V\mapsto \mathbb{R}$ and $\pi :V\mapsto V\cup \{\text{null}\}$ be attributes that we will maintain for every vertex. Initially, $\pi (v)=\text{null}$ and $d(v)=\{\begin{array}{ll}0& v=s\\ \mathrm{\infty }& v\ne s\end{array}$.

Relaxation of the edge $(u,v)$ is the following operation: If $d(v)>d(u)+w(u,v)$, set $d(v)$ to $d(u)+w(u,v)$ and $\pi (v)$ to $u$. It is easy to see that right after relaxing $(u,v)$, $d(v)\le d(u)+w(u,v)$.

When $G$ is undirected, relaxation of $(u,v)$ means relaxing in both the $(u,v)$ and $(v,u)$ directions.

Let $G_{\pi }=(V_{\pi },E_{\pi })$ where $V_{\pi }=\{v\in V:\pi (v)\ne \text{null}\}\cup \{s\}$ and $E_{\pi }=\{(\pi (v),v):v\in V\wedge \pi (v)\ne \text{null}\}$. We will soon prove that $(v\in V\wedge \pi (v)\ne \text{null})⟹\pi (v)\in V_{\pi }$, which is necessary and sufficient for $G_{\pi }$ to be a valid graph.

$G_{\pi }$ is a subgraph of $G$, since $(u,v)\in E_{\pi }$ $⟹\pi (v)=u$ $⟹(u,v)$ was relaxed $⟹(u,v)\in E$. Therefore, $G_{\pi }$ is called a predecessor subgraph of $G$ with source $s$.

While relaxations are iteratively applied to $G$, the following properties hold:

• Monotonicity: $d$ never increases with time.
• Upper-bound property: $d$ upper-bounds $\delta$.
• Reachability: $v$ is not reachable from $s$ $⟹\delta (v)=\mathrm{\infty }$ $⟹d(v)=\mathrm{\infty }$ by the upper-bound property.
• $v\in V_{\pi }⟺d(v)\ne \mathrm{\infty }$.
• $(v\in V\wedge \pi (v)\ne \text{null})⟹\pi (v)\in V_{\pi }$.

Since $d$ is an upper-bound on $\delta$, it is called the shortest-path-length estimate of $v$.

Proof

Monotonicity

On relaxing $(u,v)$, $v$ is the only vertex for which $d$ changes. In an operation of the form 'if $A>B$, set $A$ to $B$', $A$ cannot increase. Therefore, $d(v)$ cannot increase. Therefore, for every vertex $v$, $d(v)$ cannot increase with time.

Upper-bound property

Initially, $d$ is an upper-bound on $\delta$, since $d(s)=\delta (s)=0$ and $d(v)=\mathrm{\infty }\ge \delta (v)$ for all $v\ne s$.

We will prove that if the upper bound property holds before relaxing $(u,v)$, it also holds after relaxing $(u,v)$.

After relaxing $(u,v)$, if $d(v)$ changed, then $$\begin{array}{rl}d(v)& =d(u)+w(u,v)\\ & \ge \delta (u)+\delta (u,v)\\ \text{(triangle inequality of }\delta \text{)}& & \ge \delta (v)\end{array}$$

Membership in $V_{\pi }$

$v\in V_{\pi }⟺(v=s\vee \pi (v)\ne \text{null})$.

$v=s⟹d(v)=0\ne \mathrm{\infty }$.
$\pi (v)\ne \text{null}⟹(u,v)$ was relaxed for some $u$. This can only happen if $d(u)+w(u,v)\ne \mathrm{\infty }$. Therefore, after $(u,v)$ is relaxed, $d(v)\le d(u)+w(u,v)\ne \mathrm{\infty }$.
Therefore, $v\in V_{\pi }⟹d(v)\ne \mathrm{\infty }$.

$v\notin V_{\pi }$
$⟹(v\ne s\wedge \pi (v)=\text{null})$
$⟹(u,v)$ was never relaxed for any $u$ and $v\ne s$.
$⟹d(v)=\mathrm{\infty }$.

Therefore, $v\in V_{\pi }⟺d(v)\ne \mathrm{\infty }$.

Proof of $(v\in V\wedge \pi (v)\ne \text{null})⟹\pi (v)\in V_{\pi }$

Let $\pi (v)=u\ne \text{null}$. This means $(u,v)$ was relaxed. This could have only happened if $d(u)\ne \mathrm{\infty }$. Therefore, $u\in V_{\pi }$.

Dependency for:

1. Dijkstra's algorithm
2. Edge relaxations: Predecessor subgraph is a rooted tree
3. Edge relaxations: Predecessor subgraph is a shortest-path tree after convergence
4. Convergence of edge relaxations

Info:

• Depth: 3
• Number of transitive dependencies: 6

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph
6. Triangle inequality of shortest paths