MIT OpenCourseWare http://ocw.mit.edu 6.006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.6.006 Recitation Build 2008.256.006 Proudly Presents • Dijkstra: minimum-cost paths on crack • Algorithm • Concepts • Implementation • Data structures come back from the dead (not talking about the quiz)Minimum-Path Problem • Given: graph G, source vertex s, edge costs • Want: paths from s to everything else with minimum costs (sum of edge costs) • Approach: let d[v] be upper bounds for the real minimum costs, δ[v] • Start out easy: d[v] = ∞, d[s] = 0 • Relax until values in d converge to δGood Dijkstra • Generic initialization 4 B • U = V 04 • Choose v = argmin d[v in U], remove v from U 1 2 1 • Notice d[v] = δ[v] 2 1 • Relax v’s outgoing edges D 3 • Rinse, repeat S A C EBad Dijkstra • Generic initialization • U = V • Choose v = argmin d[v in U], remove v from U • Notice d[v] = δ[v] • Relax v’s outgoing edges S A B C D -54 2 1 11 • Rinse, repeatDijkstra Overview • Nice and fast (that’s why it’s on crack) • With limitations (crack impacts judgement) • Doesn’t handle negative-cost edges • DOES handle 0-cost edges • Harder to code than Bellman-FordDijkstra Works: IntuitionDijkstra Works: FormalMaking Dijkstra Fast (its crack dealer) • Generic initialization: • Computing argmin d[v]←∞, d[S] = 0 • V times • Choose v = argmin d[v], by now d[v] = δ[v] • Relaxing • Relax all edges going out • E times of v • Looks like we need a • Rinse, repeat Data StructureMin-Priority Queues • Data Structure • insert(key) : adds to the queue • min() : returns the minimum key • delete-min() : deletes the min key • delete(key) : deletes the given key • optional (only needed in some apps)Priority Queues with Min-Heaps • Costs (see above line for explanations) • insert: O(log(N)) • min: O(1) • delete-min: O(log(N)) • delete: O(log(N)) - only if given the index of the node containing the keyPriority Queues with PS3 • Is this priority queue monotone? • ProfitCool Python: Generators 1. Iterators • used in for loops • objects implementing next() 2. Generators • express iterator functionality in a cooler way 1 def counter(): 2 i = 0 3 while True: 4 yield i 5 i += 1 ----c = counter()c.next() >> 0 c.next() >> 1 d = counter() d.next()>> 0 c.next()>> 2 d.next()>> 1 c.next()>> 3Dijkstra-Ready Priority Queues 1 class heap_id: 2 def __init__(self): 3 self.A = [None] 4 self.heapsize = 0 5 self.ID_to_index = {} 6 self._ID = self._ID_generator() 7 def insert(self, key): 8 """Returns an ID that is associated with the item.""" 9 self.heapsize += 1 10 ID = self._ID.next() 11 self.ID_to_index[ID] = self.heapsize 12 self.A.append( [positive_infinity(), ID] ) 13 self.decrease_key(self.heapsize, key) 14 return ID 15 def _ID_generator(self): 16 ID = 0 17 while True: 18 yield ID 19 ID += 1Dijkstra-Ready Priority Queues II 1 class heap_id: 2 def decrease_key_using_id(self, ID, key): 3 """Decrease key given ID.""" 4 self.decrease_key(self.ID_to_index[ID], key) 5 def extract_min(self): 6 """Extracts min and returns key.""" 7 return self.extract_min_with_id()[0] 8 def extract_min_with_id(self): 9 """Extracts min and returns (key,ID) pair.""" 10 if self.heapsize < 1: 11 print "error: empty heap" 12 return 13 self._swap(1, self.heapsize) 14 self.heapsize -= 1 15 min_pair = self.A.pop() 16 del self.ID_to_index[min_pair[1]] 17 self.min_heapify(1) 18 return
View Full Document
Unlocking...