### **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