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

Find the 14th term in the arithmetic sequence. 60, 68, 76, 84, 92

how do you solve a homogeneous ode that''s not in a multiplication or division form

The position of an object at any time t (in hours) is specified by, s (t ) = 2t 3 - 21t 2 + 60t -10 Find out when the object is moving to the right and whiles the object

The Central Limit Theorem  The theories was introduced by De Moivre and according to it; if we choose a large number of simple random samples, says from any population and find

Computation method           Whereas L = Lower class boundary of the class having the mode             f 0 = Frequency of the class below the modal class

Example of Subtraction of Fractions: 1/3 + 1/6 + 1/8 = ____ Using trial & error we could search that 24 is the LCD or smallest number in which 3, 6, and 8 will all divide w

what is product life cycle

I need help with prime factors.

Basic "computation" formulas : Next, let's take a quick look at some basic "computation" formulas that will let us to actually compute some derivatives. Formulas 1)   If f