24-1 Yen's improvement to Bellman-Ford

Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as follows. Before the first pass, we assign an arbitrary linear order $v_1, v_2, \ldots, v_{|V|}$ to the vertices of the input graph $G = (V, E)$. Then, we partition the edge set $E$ into $E_f \cup E_b$, where $E_f = \{(v_i, v_j) \in E: i < j\}$ and $E_b = \{(v_i, v_j) \in E: i > j\}$. (Assume that $G$ contains no self-loops, so that every edge is in either $E_f$ or $E_b$.) Define $G_f = (V, E_f)$ and $G_b = (V, E_b)$.

a. Prove that $G_f$ is acyclic with topological sort $\langle v_1, v_2, \ldots, v_{|V|} \rangle$ and that $G_b$ is acyclic with topological sort $\langle v_{|V|}, v_{|V| - 1}, \ldots, v_1 \rangle$.

Suppose that we implement each pass of the Bellman-Ford algorithm in the following way. We visit each vertex in the order $v_1, v_2, \ldots, v_{|V|}$, relaxing edges of $E_f$ that leave the vertex. We then visit each vertex in the order $v_{|V|}, v_{|V| - 1}, \ldots, v_1$, relaxing edges of $E_b$ that leave the vertex.

b. Prove that with this scheme, if $G$ contains no negative-weight cycles that are reachable from the source vertex $s$, then after only $\lceil |V| / 2 \rceil$ passes over the edges, $v.d = \delta(s, v)$ for all vertices $v \in V$.

c. Does this scheme improve the asymptotic running time of the Bellman-Ford algorithm?

a. Assume for the purpose contradiction that $G_f$ is not acyclic; thus $G_f$ has a cycle. A cycle must have at least one edge $(u, v)$ in which $u$ has higher index than $v$. This edge is not in $E_f$ (by the definition of $E_f$), in contradition to the assumption that $G_f$ has a cycle. Thus $G_f$ is acyclic.

The sequence $\langle v_1, v_2, \ldots, v_{|V|} \rangle$ is a topological sort for $G_f$, because from the definition of $E_f$ we know that all edges are directed from smaller indices to larger indices.

The proof for $E_b$ is similar.

b. For all vertices $v \in V$, we know that either $\delta(s, v) = \infty$ or $\delta(s, v)$ is finite. If $\delta(s, v) = \infty$, then $v.d$ will be $\infty$. Thus, we need to consider only the case where $v.d$ is finite. There must be some shortest path from $s$ to $v$. Let $p = \langle v_0, v_1, \ldots, v_{k - 1}, v_k \rangle$ be that path, where $v_0 = s$ and $v_k = v$. Let us now consider how many times there is a change in direction in $p$, that is, a situation in which $(v_{i - 1}, v_i) \in E_f$ and $(v_i, v_{i + 1} \in E_b$ or vice versa. There can be at most $|V| - 1$ edges in $p$, so there can be at most $|V| - 2$ changes in direction. Any portion of the path where there is no change in direction is computed with the correct $d$ values in the first or second half of a single pass once the vertex that begins the no-change-in-direction sequence has the correct $d$ value, because the edges are relaxed in the order of the direction of the sequence. Each change in direction requires a half pass in the new direction of the path. The following table shows the maximum number of passes needed depending on the parity of $|V| - 1$ and the direction of the first edge:

$$\begin{array}{lll} |V| - 1 & \text{first edge direction} & \text{passes} \\ \hline \text{even} & \text{forward} & (|V| - 1) / 2 \\ \text{even} & \text{backward} & (|V| - 1) / 2 + 1 \\ \text{odd} & \text{forward} & |V| / 2 \\ \text{odd} & \text{backward} & |V| / 2 \end{array}$$

In any case, the maximum number of passes that we will need is $\lceil |V| / 2 \rceil$.

c. This scheme does not affect the asymptotic running time of the algorithm because even though we perform only $\lceil |V| / 2 \rceil$ passes instead of $|V| - 1$ passes, it is still $O(V)$ passes. Each pass still takes $\Theta(E)$ time, so the running time remains $O(VE)$.