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 code with generator matrix , 1. Consider the code of size 4 (4 codew...

1. Consider the code of size 4 (4 codewords) and of length 10 with codewords listed below. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1

Determinarte, what is the differeance in between determinate and matrix .

what is the differeance in between determinate and matrix .

Fraction, Ask question #Minimum 100 words accepted

Ask question #Minimum 100 words accepted

How many checks required to be used for the monthly costs, Green Bank charg...

Green Bank charges a monthly fee of $3 for a checking account and $.10 per check. Savings-R-Us bank charges a $4.50 monthly fee and $.05 per check. How many checks required to be u

Example of pythagorean theorem, Any 15 foot ladder is resting against the w...

Any 15 foot ladder is resting against the wall. The bottom is at first 10 feet away from the wall & is being pushed in the direction of the wall at a rate of 1 ft/sec. How rapid is

Matrix, parts of matrix and functions

parts of matrix and functions

Simple harmonic motion, prove that the composition of two simple harmonic o...

prove that the composition of two simple harmonic of the same period and in the same straight line is also a simple harmonic motion of the same period.

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