Relationship between the shortest path distances - tree, Mathematics

1. a)  Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same.  Do this by using potentials: 

i)  Show there is a potential y* for the new costs for which the paths in the tree to each node v have cost  y*v, and

ii) explain why this proves it.  What is the  relationship between the shortest path distances of the modified problem and those of the original problem?   

b) Can adding a constant k to the length of every arc coming out from a non-root node  produce a change in the shortest path tree?  Justify your answer.

Posted Date: 3/22/2013 3:59:36 AM | Location : United States







Related Discussions:- Relationship between the shortest path distances - tree, Assignment Help, Ask Question on Relationship between the shortest path distances - tree, Get Answer, Expert's Help, Relationship between the shortest path distances - tree Discussions

Write discussion on Relationship between the shortest path distances - tree
Your posts are moderated
Related Questions
If a single person makes $25,00 a year, how much federal income tax will he or she have to pay ?And they are gining me a chart that says $0 to $27,050 is 15% of taxes .

simplify mn+mp+nq+pq /n+p

Prove that one of every three consecutive integers is divisible by 3. Ans: n,n+1,n+2 be three consecutive positive integers We know that n is of the form 3q, 3q +1, 3q +

The student council bought two various kinds of candy for the school fair. They purchased 40 pounds of candy at $2.15 per pound and x pounds at $1.90 per pound. What is the total n

One-to-one function: A function is called one-to-one if not any two values of x produce the same y.  Mathematically specking, this is the same as saying,  f ( x 1 ) ≠ f ( x 2

CONSTANTS OF INTEGRATION Under this section we require to address a couple of sections about the constant of integration. During most calculus class we play pretty quick and lo

Find the remainder when 7^103 is divided by 24 Solution) we know by the concept of mod that.....   49 is congruent to 1 mod 24(means if 1 is subtracted fom 49 u get 48 which is

Suppose that we know the logarithms of all numbers which are expressed to base 'a' and we are required to find the logarithms of all these numbers to base 'b'. We

write and solve a problem of multiplacation that uses: estimate explaning numbers picturs and another operation?

how is it done