Relationship between shortest path distances of modified, Data Structure & Algorithms

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/28/2013 2:43:21 AM | Location : United States







Related Discussions:- Relationship between shortest path distances of modified, Assignment Help, Ask Question on Relationship between shortest path distances of modified, Get Answer, Expert's Help, Relationship between shortest path distances of modified Discussions

Write discussion on Relationship between shortest path distances of modified
Your posts are moderated
Related Questions
You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

How sparse matrix stored in the memory of a computer?

Q. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (

Q. The system allocates the memory for any of the multidimensional array from a big single dimensional array. Describe two mapping schemes that help us to store the two dimensi

Suppose you are given the results of 5 games of rock-paper-scissors. The results are given to you on separate pieces of paper; each piece says either 'A' if the first person won, o

This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of app

What is Algorithm A finite sequence of steps for accomplishing some computational task. An algorithm should Have steps which are simple and definite enough to be done

1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where

Q. Describe the adjacency matrix and make the same for the given undirected graph.    Ans: The representation of Adjacency Matrix: This representation consists of

Thus far, we have seen the demonstration of a single queue, but several practical applications in computer science needs several queues. Multi queue is data structure in which mult