patternMinor
Find the minimum path to every vertex using Bellman-Ford
Viewed 0 times
paththebellmanvertexminimumeveryfordusingfind
Problem
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.
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.
Solution
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:
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.
Context
StackExchange Computer Science Q#90991, answer score: 2
Revisions (0)
No revisions yet.