CIT 596 - HW6

This homework deals with the following topics

* Dijkstra’s algorithm.

You are allowed to collaborate for this HW. Same rules as always (max # of collaborators not including yourself is 2). You can use whatever means of communication is necessary.

Please read these instructions

• The homework has to be submitted in electronic form. as a pdf file. You can use any editing software you want in order to produce the pdf. Handwritten solutions get a 0.

• If a question asks you for an algorithm (and a time complexity is not specified in the question itself), we expect you to write pseudocode and analyze the algorithm in terms of big-O time complexity.

• As with all HWs, remember not to sacrifice correctness while striving for efficiency.

• We will not worry about the distinction between O and Θ. As long as you provide a tight bound (for example if an algorithm is actually O(n log n) and you say O(n 3 ) you will lose points) you are fine.

• Unless otherwise

• If you have any doubts on whether you are making assumptions about ‘in-built’ func-tions, please ask us on Ed. You are also strongly advised to read Piazza.

• The number of points associated with a question is a general guideline for toughness and/or amount of writing we expect. Sometimes a question might be worth 4 or 5 points only because it is lengthy.

• A result shown in class and/or provided by the textbook (Algorithms Unlocked) can be used as is. The same goes for pseudocode that you want to just use as is.

• You are allowed to write things like ”Run bfs” or ”Run dfs”. Remember that if you do so, we will assume you mean the standard (as per the textbook/lecture) algorithm. If you want to modify an algorithm then it is your job to write out the full pseudocode. You are allowed to use the pseudocode from the textbook/notes as a starting point.

Questions

1. (10 points) The edge weights on the graph represent the cost of flying between the airports that are being represented as vertices. Assuming we decide to depart from PHL (Philly), run Dijkstra’s algorithm to find the cheapest routes to every other airport. Just show how the shortest array, the predecessor array and the set of vertices (what we called Q) change in each iteration. Please be patient as you go through the steps here. A small mistake will cause problems in subsequent steps.

2. (5 points) We have been told that Dijkstra’s algorithm does not necessarily work when there are negative edges. Construct an example graph with at least 4 vertices and at least 5 edges and no negative cycles where due to one or more negative edges Dijkstra’s algorithm does not work. That is, at the end of Dijkstra’s algorithm you get incorrect answers for the shortest path.

A negative cycle is one where if you were to sum up the edge weights of the edges that are part of the cycle, you will get a negative number.

Please use the version of the algorithm that is there in the textbook - Algo-rithms Unlocked.

Run Dijkstra’s algorithm on your example (along the lines of what was done in class) and show what the final result will be. Also tell us where Dijkstra got it wrong. That is, point out a vertex where Dijkstra says the shortest path has length x and the true shortest path is something definitely less than x.

3. (5 points) Provide a counterexample to the following suggestion for handling negative edge weights in Dijkstra’s algorithm.

“Assume the source vertex is s. Assume the most negative weight is −ω where ω is some positive number. Then go ahead and add ω + 1 weight to every single edge to turn every weight into some positive weight. Now use Dijkstra’s algorithm as per usual.”

Draw the graph out. It obviously has to have some negative edges. Then use the above suggestion and show us why Dijkstra will still get it wrong.

4. (7 points) A weighted graph G=(V,E) is given to you as an adjacency list. You are also told that there is only one edge (u, v) that has a negative weight. You are given what u and v are.

WEAPARTE to find the shortest paths from a source s to all other vertices. Note that the source is a vertex that is different from u and v.