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 value of y that minimizes the sum of the two distances from (3,5) to (1,y) and from (1,y) to (4,9) can be written as a/b where a and b are coprime positive integers. Find a+b.

Evaluate following limits. Solution Let's begin with the right-hand limit.  For this limit we have, x > 4  ⇒          4 - x 3   = 0      also, 4 - x → 0  as x → 4

Question: Consider a digraph D on 5 nodes, named x0, x1,.., x4, such that its adjacency matrix contains 1's in all the elements above the diagonal A[0,0], A[1,1], A[2,2],.., e

By which of those ancient civilizations was Machu Pichu built? The Aztecs The Egyptians The Mayas The Incas Which state sold Corsica to France in 1768? - Not answered Genoa Veni

Finite Population Correction Factor Or Fpcf) If a specified population is relatively of small size and sample size is more than 5 percent of the population then the standard er

Exponential Functions : We'll begin by looking at the exponential function,                                                              f ( x ) = a x We desire to differe

if theta is a positive acute angle and 2sin theta +15cos square theta=7 then find the value of cot theta

how do i write a conjecture about the sum of two negative integers.

use the Pythagorean Theorem to find the length of the missing side. Then find the indicated trigonometric function of the given angle. give an exact answer with a rational denomina

Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20 substandard?