Introduction to Algorithms: 6.006Massachusetts Institute of Technology April 6, 2010Professors Piotr Indyk and David Karger Problem Set 5Problem Set 5This problem set is divided into two parts: Part A problems are theory questions, and Part Bproblems 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 scannedhandwritten 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 solutionwhich is described clearly. Convoluted and obtuse descriptions might receive low marks, evenwhen 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 21st1. (20 points) Graph Examples(a) (6 points) Give an example of a graph that has some shortest path from vertex s tovertex v, such that for all non-zero (positive or negative) real c, if c is added to theweights 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’salgorithm 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 nonegative-weight cycles such that if Bellman-Ford is run on this graph with the modifiedRELAX function, it will not return the correct π outputs.2. (15 points) Even-Length PathsAn even-length path is a path traversing an even number of edges. Describe a modifiedversion 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 G0that is somehow related to G, runningDijkstra’s algorithm on G0, and projecting the results back onto G.)3. (15 points) Shortest Paths with Negative-Weight CyclesG = (V, E) is a directed graph that contains at least one negative-weight cycle. Give anO(V E)-time algorithm that labels each vertex v with the shortest-path distance from source2 Problem Set 5vertex s to v, −∞ if there the shortest-path distance is undefined because of a negative-weight cycle, and ∞ if v is not reachable from s.Part B: Due Friday, April 23rd1. (50 points) Speeding up Dijkstra.The Howe & Ser Moving Company is transporting the Caltech Cannon from Caltech’s cam-pus to MIT’s and wants to do so most efficiently. Fortunately, you have at your disposal theNational Highway Planning Network (NHPN), packaged for you in ps5_dijkstra.zip.You can learn more about the NHPN athttp://www.fhwa.dot.gov/planning/nhpn/This data includes node and link text files from the NHPN. Open nhpn.nod and nhpn.lnkin a text editor to get a sense of how the data is stored (datadict.txt has a more precisedescription of the data fields and their meanings). To save you the trouble of parsing thesestructures from a file, we have provided you with a Python module nhpn.py containingcode to load the text files into Node and Link objects. Read nhpn.py to understand theformat 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 Dijk-stra’s algorithm in order to compute shortest paths between various pairs of locations.Implementation of Dijkstra’s algorithm is already provided. Functiondijkstra(nodes, edges, weight, source)is given a graph with non-negative edges (represented as a list of Node objects and a list ofundirected Edge objects), a function weight(node1, node2) that returns the weight ofany edge between node1 and node2, and a source node source. This function updatesthe node.visited field for all nodes, which indicates whether a shortest path to nodehas been found, as well as node.distance and node.parent for visited nodes, whichare the length of the shortest path from the source node to node and the previous node onthat path respectively. The function returns the number of nodes visited during the executionof the algorithm.The links you are given do not include weights, so instead we use the geographical distancebetween their endpoints. Function distance(node1, node2) returns the distance be-tween 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 be-tween 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 anitem in the heap, and Dijkstra’s algorithm would have no way of knowing the current indexcorresponding to a particular Node. To solve this problem, the course staff have written anaugmented 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 al-gorithms. You can use the Visualizer class to produce a KML (Google Earth) file. Toview such a file on Google Maps, place it in a web-accessible location, such as your AthenaPublic 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 theproblem, check your work by running the appropriate test functions. We have providedseveral test functions that test each part separately or perform comparison tests of severalmethods. You should follow the instructions for each part of the problem, perform appro-priate tests and draw conclusions. Please submit the modified dijkstra.py file with thecode 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.pyto learn the structure of the Node and Link classes and the implementation of Dijkstra’salgorithm. Run
View Full Document
Unlocking...