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

Ask an Expert

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

Write your message here..

Related Questions

Write a program to create a heap file, Write a program to create a heap fil... 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

Write an algorithm to find outputs number of cars, A company is carrying ou... 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

Small program on Algorithms , Objective The goal of this project is to ext... 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, Searching is the procedure of looking for something: Finding one... 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

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

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

Define big theta notation, Define Big Theta notation Big Theta notati... 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

Deletion of a node from a binary search tree, The algorithm to delete any n... 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,

Complexity of an algorithm, compare two functions n and 2n for various valu... 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, The searching... The searching technique that takes O (1) time to find a data is    Hashing is used to find a data