Estimate cost of an optimal diapath, Data Structure & Algorithms

Normally a potential y satisfies yr = 0 and 0 ³ yw - cvw -yv. Given an integer K³0, define a K-potential to be an array y that satisfies yr = 0 and K ³ yw - cvw -yv. Show that for a K-potential y we have that for each node v, yv is within Kn of being the cost of an optimal r-v dipath, i.e. show c(P) + Kn ³ yv for any r to v dipath P in G. HINT: Generalize our proposition from class that said that for a normal potential y, c(P)³yv for any r to v dipath P in G.

 

Posted Date: 3/28/2013 2:46:53 AM | Location : United States







Related Discussions:- Estimate cost of an optimal diapath, Assignment Help, Ask Question on Estimate cost of an optimal diapath, Get Answer, Expert's Help, Estimate cost of an optimal diapath Discussions

Write discussion on Estimate cost of an optimal diapath
Your posts are moderated
Related Questions
Consistent Heuristic Function - Graph Search Recall the notions of consistency and admissibility for an A* search heuristic. a. Consider a graph with four nodes S, A, B, C,

Merging 4 sorted files having 50, 10, 25 and 15 records will take time  O (100)

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

Q. Make a BST for the given sequence of numbers. 45,32,90,34,68,72,15,24,30,66,11,50,10 Traverse the BST formed in  Pre- order, Inorder and Postorder.

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5


Explain binary search with an example