This is the 24.1-5 question in CLRS. I'm having a hard time understanding the questions and also how to solve it. δ(u,v) is defined as the shortest path weight from u to v if there exist a path from u to v.

This is the 24.1-5 question in CLRS. I'm having a hard time understanding the questions and also how to solve it. δ(u,v) is defined as the shortest path weight from u to v if there exist a path from u to v.

Let G=(V,E) be a weighted, directed graph with weight function w:E→R. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}.

What I'm confusing about this question is what is δ∗(v) suppose to be. I also found the answer online but still don't really understand why it is like that. Since this is an exercise in the Bellman-Ford algorithm of CLRS. the answer said to change the RELAX operation of the algorithm. The RELAX operation in Bellman-Ford is what help achieve the shortest path weight after you run this V time for each edge in E.

the ORIGINAL-RELAX operation supposes to be like this:

RELAX(u, v, w) if v.d > u.d + w(u,v) v.d = u.d + w(u,v) v.pi = u.pi 

With v.d and u.d being the upper bound for the shortest path from source to u and v. v.pi is supposed to be its predecessor for the current upper bound.

The answer said to change the RELAX operation to this.

MOD-RELAX(u, v, w) if v.d > min(w(u, v), w(u, v) + u.d) v.d = min(w(u, v), w(u, v) + u.d) v.pi = u.pi 

I need some explaination to what the problem is asking for and why this answered it.