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
Here,  m represents the unordered array of elements n  represents number of elements in the array and el  represents the value to be searched in the list Sep 1: [Initialize]

write a pseudocode to input the top speed (in km''s/hours) of 5000 cars output the fastest speed and the slowest speed output the average (mean) speed of all the 5000 cars answers

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

explain the determination of interest rate in the classical system.

The insertion procedure in a red-black tree is similar to a binary search tree i.e., the insertion proceeds in a similar manner but after insertion of nodes x into the tree T, we c

Q. How do we represent a max-heap sequentially? Explain by taking a valid   example.         Ans: A max heap is also called as a descending heap, of size n is an almos

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

There are three typical ways of recursively traversing a binary tree. In each of these, the left sub-trees & right sub-trees are visited recursively and the distinguishing feature