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
Limitation of Binary Search: - (i)  The complexity of Binary search is O (log2 n). The complexity is similar irrespective of the position of the element, even if it is not pres

Define data model?  A data model is a collection of conceptual tools for explaning data, data relationships, data semantics and consistency constraints.

what is tower of management with example

example of stack using flowchart

what is folding method?

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements

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

The number of interchanges needed to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is 5

If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your mission (sho

Q. Write  down the  algorithm  to  insert  an  element  to  a  max-heap  which  is  represented sequentially.           Ans: The algorithm to insert an element "newkey" to