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
Write a program to create a heap file that holds the records in the file " data_2013 " The source records are variablelength.However, the heap file should hold fixed-length reco

A company is carrying out a survey by observing traffic at a road junction. Every time a car, bus or lorry passed by road junction it was noted down. 10 000 vehicles were counted d

Objective The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The ass

Searching is the procedure of looking for something: Finding one piece of data that has been stored inside a whole group of data. It is frequently the most time-consuming part of m

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

write a program that find,search&replace a text string

Define Big Theta notation Big Theta notation (θ) : The upper and lower bound for the function 'f' is given by the big oh notation (θ). Considering 'g' to be a function from t

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

compare two functions n and 2n for various values of n. determine when second becomes larger than first

The searching technique that takes O (1) time to find a data is    Hashing is used to find a data