Find the minimum path to every vertex using Bellman-Ford

Question

I was studying the chapter 24 of the CLRS and got to the following question:

24.1-5 $\star$ Let $G=(V,E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb{R}$. Give an $O(VE)$-time algorithm to find, for each vertex $v \in V$, the value $\delta^{*}(v) = \min_{u \in V}\{\delta(u,v)\}$.

From what I understood, he wants an algorithm to find the shortest path beginning in any $u \in V-\{s\}$ to every vertex $v \in V$. So, this algorithm would return one shortest path for each vertex in $V$ in $O(|V||E|)$. I couldn't come with any other answer besides using an All-Pairs Shortest Paths algorithm and choosing the paths with less value for each vertex. But, as this chapter is about the Bellman-Ford, this is probably some modification from the original algorithm.

If someone could point me in the right direction, I would really appreciate.

Answer 1

The algorithm is very similar to Bellman-Ford algorithm except that for each vertex $v$, you maintain $\delta^*(v)$, while in Bellman-Ford algorithm you maintain the length of shortest path from a certain source to $v$.

The correctness of the proof is also similar to that of Bellman-Ford algorithm. More specifically, you prove the following lemma by mathematical induction.

Lemma. After $i$ repetitions of for loop:

• If $\mathrm{Distance}(u)$ is not infinity, it is equal to the length of some path from to $u$;
• If there is a path to $u$ with at most $i$ edges, then $\mathrm{Distance}(u)$ is at most the length of the shortest path to $u$ with at most $i$ edges.

Answer 2

You are not parsing this right. The text of the exercise uses $\delta$ implicitly; traditionally $\delta(uv)$ in the context of graph theory stands for the minimum distance metric. Since the exercise makes perfect sense assuming this definition, I will go along with it.

What the problem asks you to do, in other words, is to compute a function $\delta^*(v)$, defined on all $v \in V$ as the minimum weight $x$ such that there exists a node $u$ for which $\delta(uv) = x$.

I will outline a sketch of the solution, leaving the details to you.

First of all, observe that $\delta^*(v) \le 0$ since $\delta(vv) = 0$. Furthermore, by subadditivity of $\delta$, it is easy to verify that $\delta^*(v) \le \delta^*(w) + \delta(vw)$.

Construct the transpose graph $G^T = (V, \{(u, v) \mid (v, u) \in E\})$. Computing $\delta^*$ on $G$ is equivalent to computing $\delta^{*T}(v) = \min_{u\in V} \{ \delta(vu) \}$ on $G^T$.

First, assume that $G^T$ has no negative-weight cycles, we will deal with this case later. If there are no negative-weight cycles, the shortest paths are acyclic, therefore we can use our second observation from above to compute $\delta^{*T}$ as follows:

• For all $v \in V$ set $\delta^{*T}(v) =0$.
• For $i := 0$ to $|V|-1$ use each edge $uv \in |E|$ to "relax" $\delta^{*T}(u).$

The above procedure yields a correct result for all nodes of $G^T$ that don't reach any negative cycle. Nodes that do reach a negative cycle should be labelled by $-\infty$. We have to find all such nodes to complete our algorithm.

In order to do that,

• Compute $G^{SCC}$, the graph of the strongly connected components of $G$. Each negative cycle must be entirely included in one of those components.

• Run Bellman-Ford on each component to find those which contain negative cycles. Note that the total running time of this step is $O(|V||E|)$ because, assuming the $i$-th connected component has nodes $V_i$ and edges $E_i$, the inequality: $\sum |V_i||E_i| \le \sum|V_i| \sum|E_i| = |V||E|$ holds by Cauchy-Schwarz.

• A node $u$ reaches $v$ in $G^T$ if and only if the equivalence class of $v$ reaches the equivalence class of $u$ in $G^{SCC}$: use a reachability algorithm to find all those nodes.

Piecing together the two parts yields a solution to the original question.