Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Piotr Indyk and David Karger April 6 2010 Problem Set 5 Problem Set 5 This problem set is divided into two parts Part A problems are theory questions and Part B problems are programming tasks Part A questions are due Wednesday April 21st at 11 59PM Part B questions are due Friday April 23rd at 11 59PM Solutions should be turned in through the course website in PDF form using LATEX or scanned handwritten solutions A template for writing up solutions in LATEX is available on the course website Remember your goal is to communicate Full credit will be given only to the correct solution which is described clearly Convoluted and obtuse descriptions might receive low marks even when they are correct Also aim for concise solutions as it will save you time spent on write ups and also help you conceptualize the key idea of the problem Part A Due Wednesday April 21st 1 20 points Graph Examples a 6 points Give an example of a graph that has some shortest path from vertex s to vertex v such that for all non zero positive or negative real c if c is added to the weights of all the edges that path is no longer a shortest path from s to v b 6 points Give an example of a graph with negative weight edges for which Dijkstra s algorithm gives incorrect answers c 8 points Suppose that the RELAX function is changed so that it updates if d v d u w u v instead of strictly greater than Give an example of a graph with no negative weight cycles such that if Bellman Ford is run on this graph with the modified RELAX function it will not return the correct outputs 2 15 points Even Length Paths An even length path is a path traversing an even number of edges Describe a modified version of Dijkstra s algorithm that finds the shortest even length path in a graph G V E from a given start vertex s to all vertices t V The graph has non negative edge weights Your solution should have the same asymptotic running time as Dijkstra s algorithm HINT try solving the problem by constructing a graph G0 that is somehow related to G running Dijkstra s algorithm on G0 and projecting the results back onto G 3 15 points Shortest Paths with Negative Weight Cycles G V E is a directed graph that contains at least one negative weight cycle Give an O V E time algorithm that labels each vertex v with the shortest path distance from source 2 Problem Set 5 vertex s to v if there the shortest path distance is undefined because of a negativeweight cycle and if v is not reachable from s Part B Due Friday April 23rd 1 50 points Speeding up Dijkstra The Howe Ser Moving Company is transporting the Caltech Cannon from Caltech s campus to MIT s and wants to do so most efficiently Fortunately you have at your disposal the National Highway Planning Network NHPN packaged for you in ps5 dijkstra zip You can learn more about the NHPN at http www fhwa dot gov planning nhpn This data includes node and link text files from the NHPN Open nhpn nod and nhpn lnk in a text editor to get a sense of how the data is stored datadict txt has a more precise description of the data fields and their meanings To save you the trouble of parsing these structures from a file we have provided you with a Python module nhpn py containing code to load the text files into Node and Link objects Read nhpn py to understand the format of the Node and Link objects you will be given Your goal in this problem is to implement and test several techniques for speeding up Dijkstra s algorithm in order to compute shortest paths between various pairs of locations Implementation of Dijkstra s algorithm is already provided Function dijkstra nodes edges weight source is given a graph with non negative edges represented as a list of Node objects and a list of undirected Edge objects a function weight node1 node2 that returns the weight of any edge between node1 and node2 and a source node source This function updates the node visited field for all nodes which indicates whether a shortest path to node has been found as well as node distance and node parent for visited nodes which are the length of the shortest path from the source node to node and the previous node on that path respectively The function returns the number of nodes visited during the execution of the algorithm The links you are given do not include weights so instead we use the geographical distance between their endpoints Function distance node1 node2 returns the distance between two NHPN nodes Nodes come with latitude and longitude in millionths of degrees For simplicity we treat these as x y coordinates on a flat surface where the distance between two points can be calculated using the Pythagorean Theorem Dijkstra s algorithm uses a priority queue but this priority queue has one subtle requirement Dijkstra s algorithm calls decrease key but decrease key requires the index of an item in the heap and Dijkstra s algorithm would have no way of knowing the current index corresponding to a particular Node To solve this problem the course staff have written an augmented heap object heap id with the following extra features Problem Set 5 3 insert key returns a unique ID decrease key using id ID key takes an ID instead of an index extract min with id extracts the minimum element and returns a pair key ID Additionally we have provided some tools to help you visualize the output from your algorithms You can use the Visualizer class to produce a KML Google Earth file To view such a file on Google Maps place it in a web accessible location such as your Athena Public directory and then search for its URL on Google Maps For this problem you will modify the file dijkstra py As you solve each part of the problem check your work by running the appropriate test functions We have provided several test functions that test each part separately or perform comparison tests of several methods You should follow the instructions for each part of the problem perform appropriate tests and draw conclusions Please submit the modified dijkstra py file with the code and dijkstra pdf file with proofs and short answers Keep them short a 3 points Examine the code provided in nhpn py heap py and dijkstra py to learn the structure of the Node and Link classes and the implementation of Dijkstra s algorithm Run test a Is there a significant difference in the execution time for different pairs of nodes Explain your observation b 7 points One way to speed up Dijkstra s algorithm is
View Full Document
Unlocking...