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. Since in $G_f$ edges only go from vertices with smaller index to vertices with greater index, there is no way that we could pick a vertex, and keep increasing it's index, and get back to having the index equal to what we started with. This means that $G_f$ is acyclic. Similarly, there is no way to pick an index, keep decreasing it, and get back to the same vertex index. By these definitions, since $G_f$ only has vertices going from lower indices to higher indices, $(v_1, \dots, v_{|V|})$ is a topological ordering of the vertices. Similarly, for $G_b$, $(v_{|V|}, \dots, v_1)$ is a topological ordering of the vertices.

b. Suppose that we are trying to find the shortest path from $s$ to $v$. Then, list out the vertices of this shortest path $v_{k_1}, v_{k_2}, \dots, v_{k_m}$. Then, we have that the number of times that the sequence $\{k_i\}_i$ goes from increasing to decreasing or from decreasing to increasing is the number of passes over the edges that are necessary to notice this path. This is because any increasing sequence of vertices will be captured in a pass through $E_f$ and any decreasing sequence will be captured in a pass through $E_b$. Any sequence of integers of length $|V|$ can only change direction at most $\lfloor |V| / 2 \rfloor$ times. However, we need to add one more in to account for the case that the source appears later in the ordering of the vertices than $v_{k_2}$, as it is in a sense initially expecting increasing vertex indices, as it runs through $E_f$ before $E_b$.

c. It does not improve the asymptotic runtime of Bellman ford, it just drops the runtime from having a leading coefficient of $1$ to a leading coefficient of $\frac{1}{2}$. Both in the original and in the modified version, the runtime is $O(EV)$.