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 doare transposed to read
forall i <- 1 to n do for all j <- 1 to n do for k <- 1 to n doSuppose 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
email@example.com (Richard Cole)