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

Splaying algorithm, Insertion & deletion of target key requires splaying of... Insertion & deletion of target key requires splaying of the tree. In case of insertion, the tree is splayed to find the target. If, target key is found out, then we have a duplicat

Applications of linear and binary search, The searching method are applicab... The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

System defined data types, System defined data types:- These are data t... System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

Shortest path algorithms, A driver takes shortest possible route to attain ... A driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

Simplifying assumptions of wire frame representation, Simplifying Assumptio... Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

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

What is Oscillating Sort?, For the Oscillating sort to be applied, it is ne... For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the po

Heap sort, We will start by defining a new structure called Heap. Figure 3 ... We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

Array, extra key inserted at end of array is called extra key inserted at end of array is called

Merging, merging 4 sorted files containing 50 10 25 and 15 records will tak... merging 4 sorted files containing 50 10 25 and 15 records will take time