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

Linear programming, Consider the following linear programming problem: M...

Consider the following linear programming problem: Min (12x 1 +18x 2 )             X 1 + 2x 2 ≤ 40             X 1 ≤ 50             X 1 + X 2 = 40             X

Trignometry, i have to get 10 points in 10th class

i have to get 10 points in 10th class

Integers, hi i would like to ask you what is the answer for [-9]=[=5] grade...

hi i would like to ask you what is the answer for [-9]=[=5] grade 7

Sum, what is an equation for circle?..

what is an equation for circle?..

Proof of various limit properties, PROOF OF VARIOUS LIMIT PROPERTIES In...

PROOF OF VARIOUS LIMIT PROPERTIES In this section we are going to prove several of the fundamental facts and properties about limits which we saw previously. Before proceeding

100 day countdown, subtract 20and 10,and then mutiply by 5

subtract 20and 10,and then mutiply by 5

Ratio and proportion, the sides of triangleare inthe ratio 2;3;4 if the per...

the sides of triangleare inthe ratio 2;3;4 if the perimeter is 72 cm. find its side.

Quan. literacyprofiency, 3.20 euros per kilogram, 1 kilogram =2.2 pounds an...

3.20 euros per kilogram, 1 kilogram =2.2 pounds and current exchange rate is $1=0.9 euros. what is the price per pound?

Percentage, 7 is what percent of 105?.

7 is what percent of 105?.

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