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

Slope-intercept form, Slope-intercept form The ultimate special form of...

Slope-intercept form The ultimate special form of the equation of the line is possibly the one that most people are familiar with.  It is the slope-intercept form.  In this if

Linear Programming, A garden shop wishes to prepare a supply of special fer...

A garden shop wishes to prepare a supply of special fertilizer at a minimal cost by mixing two fertilizers, A and B. The mixture is to contain at least 45 units of phosphate at lea

Multiplication of two like terms with same signs, Case 1: Suppose we...

Case 1: Suppose we have two terms 7ab and 3ab. When we multiply these two terms, we get 7ab x 3ab = (7 x 3) a 1 + 1 . b 1 + 1  ( Therefore, x m . x n = x m +

Counting, how do i count by 45s

how do i count by 45s

Proof by Condratiction, "Prove by contradiction that no root of the equatio...

"Prove by contradiction that no root of the equation x^18 -2x^13 + x^5 -3x^3 + x - 2 = 0 is an integer divisible by 3" Any help would be very much appreciated!

Arithmetic sequence, find a30 given that the first few terms of an arithmet...

find a30 given that the first few terms of an arithmetic sequence are given by 6,12,18...

Marketing, In a 2500 word report do the market analysis of China. Under thi...

In a 2500 word report do the market analysis of China. Under this you have to explain: - What are the advantages and disadvantages for foreign company to set up its business cent

Define period, Q. Define Period, Amplitude and Phase Shift? Ans. P...

Q. Define Period, Amplitude and Phase Shift? Ans. Period, amplitude and phase shift are used when describing a sinusoidal curve The period of a function is the smallest

My daugther needs help, my daughter is having trouble with math she cant un...

my daughter is having trouble with math she cant understand why please help us

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