CS 223 In-lab 11
Week of 4/17

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

The Floyd-Warshall Algorithm

The purpose of this lab is to gain more familiarity with the Floyd-Warshall algorithm for solving the all-pairs shortest path problem in a weighted graph.  We developed some initial code in class here; your task is to modify this code so that in addition to finding the shortest path distance you should also print out the complete path (print out all of the vertices along the path).

The Graph
In this example, a number of random points are placed in a box with side lengths equal to 100.  So the box stretches from (0,0) to (100,100).  We're interested in determining the shortest path from (0,0) to (100,100), provided one exists.  To see what is going on, take a look at the source code and try running it a few times.

To do this in-lab, you will need to read about how keep track of points along the path.  This is discussed on page 632 of your CLRS textbook (it also uses the procedure PRINT-ALL-PAIRS-SHORTEST-PATH given on page 621).

One important note that we talked about in class (and also mentioned in Exercise 25.2-4) is that you can get rid of the (k) superscript, so you just need to create another array called pred, the same dimensions as the dist array and fill it in according to the recurrence equation (25.7).

What to Turn In

• Source code and a printout of several runs showing the printed path.
• Approximately how many points do you need to have a pretty good chance of finding a path?