CompSci 163/265, Spring 2016, Homework 4

  1. Dijkstra's algorithm will produce an answer on all graphs, but unless the edge weights are all positive its answers might not be correct. Give an example of a graph for which Dijkstra's algorithm produces an incorrect answer. Your graph should not have any negative cycles, and it should have the property that, after all edges are relaxed in the order given by Dijkstra's algorithm, at least one tentative distance $D[v]$ is not equal to the true distance from the starting vertex. What are the values $D[v]$ computed by Dijkstra's algorithm for your graph, and what are the values that a correct algorithm would compute?

  2. Suppose that we implement the priority queue for Dijkstra's algorithm as an unordered list of vertices. For such an implementation, the priority for any vertex can be changed in constant time (by changing the number stored with that vertex) but finding and removing the minimum-priority vertex takes $O(n)$ time. For this implementation, what would be the running time of Dijkstra's algorithm? Give your answer using $O$-notation, as a function of $n$ (the number of vertices) and $m$ (the number of edges), in as simple a form as possible. You may assume that the input is a simple graph, so that $m=O(n^2)$.

  3. One step of Johnson's algorithm uses the Bellman–Ford algorithm to convert a graph with negative edge weights (but no negative cycles) into a graph with the same shortest paths but with all edge weights non-negative, in $O(mn)$ time. Suppose that the graph we are given is a DAG. Describe an alternative method for converting it to another graph with the same shortest paths but with all edge weights non-negative, in only linear time.

  4. (163 students:) Draw an undirected graph with positive edge weights, with a designated vertex $s$, such that the shortest path tree starting from $s$ is different from the minimum spanning tree of the graph. Choose your weights such that there are no ties in the computation of these trees.

    (265 students:) Draw an undirected graph with positive edge weights such that, for every vertex $s$ in your graph, the shortest path tree starting from $s$ is different from the minimum spanning tree of the graph. Choose your weights such that there are no ties in the computation of these trees.