1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ If you don't understand the question, us providing you with an answer to it won't really help you. I suggest you step back and try to understand the question, first. In particular, you can ask us about the parts you don't understand! $\endgroup$
    – David Richerby
    Jan 16, 2017 at 17:08
  • $\begingroup$ I suggest you edit the question to include the full statement of the problem, and tell us what parts you don't understand, what is confusing you, and what parts you do understand. As it stands, it's not clear how to help you understand the question, short of repeating it (and I worry you might say you didn't understand that either). The more you give us to work with, the more likely that we can give you an answer you find helpful. Also, please don't put the entire text of the exercise in the title; the title is intended to be a short summary. See meta.cs.stackexchange.com/a/815. $\endgroup$
    – D.W. ♦
    Jan 16, 2017 at 17:19
  • $\begingroup$ Sorry for the problem. I hope this edit will help you better to understand what I'm asking for. $\endgroup$
    – Tienanh Nguyen
    Jan 16, 2017 at 17:48
  • $\begingroup$ Fora vertex $v$, consider all the possible values of $\delta(u,v)$, where $u$ is any vertex in the graph. $\delta^*(v)$ is defined to be the smallest of those values. $\endgroup$
    – David Richerby
    Jan 16, 2017 at 18:32
  • $\begingroup$ Working through some examples may help -- pick a small graph, and compute the value of $\delta^*(v)$ for each $v$ by plugging into the definition. $\endgroup$
    – D.W. ♦
    Jan 16, 2017 at 19:08

1 Answer 1

Reset to default
1
$\begingroup$

What is the question?

A vertex v ∈ G.V can have shortest paths from other vertices u ∈ G.V - {v}. What is the minimum of all these paths to v? This is 𝛿*(u, v). You have to calculate this minimum value for all the vertices

Why the solution works?

To get to a vertex v you have 2 options:

  1. Take minimum incoming edge from u to v i.e. w(u, v)
  2. Get to u and then take the edge from u to v i.e. u.d + w(u, v)

You have to find the minimum of these 2 options. So min(w(u, v), u.d + w(u, v))

In either of the cases the v.pi will be u

Improve this answer
$\endgroup$
1
  • $\begingroup$ Can I have an upvote if the answer is correct? I want to comment on other posts but have a low rep $\endgroup$
    – Stuxen
    Nov 4, 2019 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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