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

Branch and bound algorithm, Suppose we have a set of N agents and a set of ... Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a

Linked List Variations, Part1: Deque and Bag Implementation First, complet... Part1: Deque and Bag Implementation First, complete the Linked List Implementation of the Deque (as in Worksheet 19) and Bag ADTs (Worksheet 22). Files Needed: linkedList.c Linke

If-then-else statements, In this example, suppose the statements are simple... In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

Quicksort and bubble sort algorithms, Task If quicksort is so quick, w... Task 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

Insertion of element into a linked list, ALGORITHM (Insertion of element in... ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t

Representation of linked list in memory, Representation of Linked list in M... Representation of Linked list in Memory:- Each node has an info part and a pointer to the next node also known as link. The number of pointers is two in case of doubly linked

Graph traversal schemes, Various graph traversal schemes Graph Traversa... Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

Adjacency matrix, Q. Give the adjacency matrix for the graph drawn below:  ... Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

The time and space complexities of an algorihm, Relation between the time a... Relation between the time and space complexities of an algorithm The examining of algorithm focuses on time complexity and space complexity. As compared to time analysis, the a

Pseudo code, I need help writing a pseudocode for my assignment can anyone ... I need help writing a pseudocode for my assignment can anyone help?