2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.