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
f(x)= 2e^5x+6 find the domain of f and find x-intercept.


The sum of two consecutive integers is 41. What are the integers? Two consecutive integers are numbers in sequence like 4 and 5 or -30 and -29, that are each 1 number apart. Le

Theorem Consider the subsequent IVP. y′ =  p (t ) y = g (t )  y (t 0 )= y 0 If p(t) and g(t) are continuous functions upon an open interval a o , after that there i

How to Solving One-Step Equations? Equations, where one math operation is acting on the variable, can be solved in one step. The trick is to get the variable x by itself - isol

You are required to implement Kruskal's algorithm for finding a Minimum Spanning Tree of Graph.  This will require implementing : A Graph Data Type (including a display meth


A painter leans a 10-foot ladder against the house she is to paint. The foot of the ladder is 3 feet from the house. How far above the ground does the ladder touch the house? Appro

A 64-ounce bottle of detergent costs $3.20. What is the cost per ounce of detergent? To ?nd out the cost per ounce, divide the cost through the number of ounces; $3.20 ÷ 64 =

The alternative hypothesis When formulating a null hypothesis we also consider the fact that the belief may be found to be untrue thus we will refuse it.  Therefore we formula