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 25 6 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 A U V Choose v argmin d v in U remove v from U Notice d v v Relax v s outgoing edges Rinse repeat B 0 4 1 S 4 2 1 2 E 1 C 3 D Bad Dijkstra Generic initialization Notice d v v A U V Choose v argmin d v in U remove v from U Relax v s outgoing edges Rinse repeat 5 4 2 S B 1 1 1 D C Dijkstra 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 Ford Dijkstra Works Intuition Dijkstra Works Formal Making Dijkstra Fast its crack dealer Generic initialization d v d S 0 Choose v argmin d v by now d v v Relax all edges going out of v Rinse repeat Computing argmin Relaxing V times E times Looks like we need a Data Structure Min 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 key Priority Queues with PS3 Is this priority queue monotone Pro t Cool 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 3 Dijkstra 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 1 Dijkstra 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 tuple min pair
View Full Document
Unlocking...