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
the function g is defined as g:x 7-4x find the number k such that kf(-8)=f- 3/2



all formulas of plane figures

One-sided limits: We do this along with one-sided limits.  As the name implies, with one-sided limits we will just looking at one side of the point in question.  Following are the

Question 1: What is the minimum number of students each of whom comes from one of the 50 different states, enrolled in a university to guarantee that there are at least 100 who

Unit circle A circle centered at the origin with radius 1 (i.e. this circle) is called as unit circle.  The unit circle is very useful in Trigonometry. (b) x 2 + ( y - 3) 2

We're here going to take a brief detour and notice solutions to non-constant coefficient, second order differential equations of the form. p (t) y′′ + q (t ) y′ + r (t ) y = 0

show that the subtangent at any point on parabola y2 =4ax is twice the abscissa at that point.

If ABCD isaa square of side 6 cm find area of shaded region