CS 163 / CS 265 Homework 4, due Friday, February 8

1. Suppose we wish to computeshortest paths in a complete directed graph (a directed graph in which there exists an edge in each direction between every two vertices), with positive edge weights (so that Dijkstra's algorithm may be used). But rather than using a complicated priority queue data structure, we use an unsorted list L of the vertices that have not yet been processed. That is, the simplified version of Dijkstra's algorithm performs the following steps:

    initialize the D and P information used by the relaxation algorithms for
    single source shortest paths

    initialize L to be a list of all the vertices in the graph

    while L is not empty:
        look at all of the vertices in L to find the vertex v with
        the minimum value of D[v]

        remove v from L

        for each edge v->w
            relax(v->w)

You may assume that looking at all vertices in L takes time proportional to the number of vertices examined, and that removing v from L takes constant time.

(a) What is the running time of this algorithm, using O-notation, as a function of the number n of vertices in the input graph?

(b) Would this algorithm be a better or worse choice than the more usual form of Dijkstra's algorithm using a binary heap, for this type of graph? Explain your answer.


2. Suppose that a graph G has the property that every shortest path from the starting vertex s to every other vertex has at most three edges. What would this fact imply about the running time of the Bellman-Ford algorithm for finding shortest paths starting from s in G?


3. Let G be a directed path with six vertices and five edges, each of which has length -1. Show the values of phi(v) for each vertex v, and of the new edge weights for each edge, that would be calculated by Johnson's algorithm on this graph.


4. Suppose you are given a directed graph (containing cycles) in which all edges have weight 1. Name an algorithm that can solve the single-source shortest path problem in this graph in linear time, without using a priority queue data structure.


5* (CS 265 students only). As well as being used to compute shortest paths, the framework of relaxation algorithms may be used for the widest path problem. However, to do so, the relax procedure needs to be modified. Give pseudocode for a modified version of relax that works for widest paths.