Relationship between the shortest path distances - tree, Mathematics

Assignment Help:

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.


Related Discussions:- Relationship between the shortest path distances - tree

Show that x(q-r) + y(r-p) + z(p-q) = 0, If the p th , q th & r th term of...

If the p th , q th & r th term of an AP is x, y and z respectively, show that x(q-r) + y(r-p) + z(p-q) = 0 Ans:    p th term ⇒ x = A + (p-1) D q th term ⇒ y = A + (

Evaluate following. 0ln (1+)excos(1-ex)dx substitution, Evaluate following....

Evaluate following. ∫ 0 ln (1 + π )   e x cos(1-e x )dx Solution The limits are little unusual in this case, however that will happen sometimes therefore don't get

Geometry, can i get some triangle congruence proofs help?

can i get some triangle congruence proofs help?

Testing the hypothesis equality of two variances, Testing the hypothesis eq...

Testing the hypothesis equality of two variances The test for equality of two population variances is based upon the variances in two independently chosen random samples drawn

Algebra, Hi, I don''t know how to solve 2(5x+3)

Hi, I don''t know how to solve 2(5x+3)

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd