Homework 9, Fundamental Algorithms, Fall 97

Due Date: Monday, November 10.

Problems 4.9, 4.10. (See back of text, page 404).

3. See pages 241-242. Suppose, in the Floyd-Warshall algorithm that that lines:

for k <- 1 to n do
  forall i <- 1 to n do
    for all j <- 1 to n do
are transposed to read
forall i <- 1 to n do
  for all j <- 1 to n do
    for k <- 1 to n do
Suppose that the transposed algorithm is run on a general graph. What paths will it consider as possible candidates for the shortest path from vertex 1 to vertex 2? Describe this path in words.

4. Let G be a weighted graph in which each edge is labelled one of a or b. An a-b path is a path in which the labels on the edges alternate, with the first edge labelled a. Give an efficient algorithm to compute the shortest a-b path from i to j for every pair i,j of vertices.

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Nov 3, 1997