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
By which of those ancient civilizations was Machu Pichu built? The Aztecs The Egyptians The Mayas The Incas Which state sold Corsica to France in 1768? - Not answered Genoa Veni

What is Exponential Functions ? Exponent Laws Review: A) Ax / Ay = A(x + y) B) Ax / Ay = A(x - y) C) (ABC)x = AxBxCx D) ((Ax)y)z = Axyz E) (A/B)x = Ax /Bx Definition

HOW MANY SHARES CAN I BUY WITH 1000 DOLLARS

The center of a national park is located at (0,0). A special nature preserve is bounded by by straight lines connecting the points A at (3,2), B at (5,1), C at (8,4) and D at (6,5)

A comparison of the wearing out quality of two types of tyres was obtained by road testing. Samples of 100 tyres were collected. The miles traveled until wear out were recorded and

explain the formular for finding trigonometry

If the normal to y=f(x) makes an angle of pie/4 with y-axis at (1,1) , then f''(x) is eqivalent to? Ans) The normal makes an angle 135 degree with the x axis. also f ''(1)

16 raised to the power x eqaual to x raised to the power 2. find x

Find the second derivative of the below given equation Y= e x cosx

Sharon purchased six adult movie tickets. She spent $43.50 on the tickets. How much was each ticket? To ?nd out the price of each individual ticket, you should divide the total