CS 163, Spring 2012, Homework 3, due Thursday, April 26

  1. Draw a directed graph, with a specified starting vertex, that has negative-length edges but no negative-length cycles, and for which Dijkstra's algorithm does not produce the correct distances to all other nodes. For which vertices in your graph does Dijkstra's algorithm give the wrong answers?

  2. Suppose you are given as input a directed graph together with a starting vertex and the correct set of distances from the starting vertex to all the other vertices, but you are not given any information about where the shortest paths go. Describe an algorithm that finds the set of all edges that belong to at least one shortest path, in linear time, from this information. (Hint: for each edge, compare the distances for its two endpoints.)

  3. Suppose that we wish to apply Johnson's algorithm to find all pairwise distances in the following graph. List for each vertex v in the graph the distance from the new node q (added by Johnson's algorithm) to v. Also list for each edge in the graph the new edge length computed by Johnson's algorithm for that edge.

  4. In the same graph drawn above, suppose we are using the Bellman-Ford algorithm to find the shortest paths from a to every other vertex. If we relax the edges in alphabetical order (that is, the edges out of vertex a first, the edges out of vertex b second, etc) then what are the tentative distances after the first iteration of the algorithm? (That is, after each edge has been relaxed exactly once.)

  5. Suppose we wish to find shortest paths from a start vertex to a goal vertex in a road network, where the length of each edge is measured by the physical length of the corresponding segment of road (not travel time). Then, the straight-line distance from a vertex v to the goal can be used as a heuristic underestimate h(v) of the road distance. But instead of using h(v) as part of the A* algorithm, we use it in a simpler way, to direct each edge of the road network from the endpoint with a larger value of h(v) to the endpoint with a smaller value. (Intuitively, we are making each segment of road one-way, in the direction that leads towards the goal.) If we use the DAG shortest path algorithm on the resulting directed graph, will it be guaranteed to find the correct shortest path in the original undirected road network? Why or why not?