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
On a piece of machinery, the centers of two pulleys are 3 feet apart, and the radius of each pulley is 6 inches. Determine the size of belt (in feet) is required to wrap around bot

can you help me with financial math??

add 1 and 20 over 40 with 2 and 30 over 50

Example of Product moment correlation The given data was acquired during a social survey conducted in a described urban area regarding the yearly income of described families

A reaction following first-order kinetics was studied by determining the reactant concentrations at equal time intervals. Each successive pair of concentrations, [A] o and [A] 1

Example of Implicit differentiation So, now it's time to do our first problem where implicit differentiation is required, unlike the first example where we could actually avoid


how to explain this strategy? how to do this strategy in solving a problem? can you give some example on how to solve this kind of strategy.

An experiment designed to test the potency of a drug on 20 rats. Last animal studies have shown that a 10 mg dose of the drug is lethal 5% of the time within the first 4 hours; of

how to know if it is function and if is relation