Floyd’s Algorithm

Project #1

CIS480

Due: See Upcoming

Assignment:

1. Write a program to implement Floyd’s Algorithm using the class handout.

2. Test your program on the weighted graph shown below.

3. Apply the program to the additional input supplied.

4. Hand in a copy of the program with output generated.

Program Operation:

Read the input which is an adjacency matrix of a simple graph with weighted edges.  An example of input is found below.  For every pair or vertices in the graph, compute the length of the shortest path  and the vertices traversed.  Output the value computed for each pair of vertices.  If the vertices were labeled with letters of the alphabet, then that should be reflected in the output, as in the sample output for Problem #2 shown below.

Program Testing:

Run your program on 3 sets of input:

    1. The Weighted Graph Example immediately below.

    2. Problem #8.6.2 of Rosen, 5^th edition.

            Input format can be either numeric, as here, or alphabetic, as here.

            Output should be alphabetic, as here.

    3. Problem #8.6.4 of Rosen. 

            Input format can be either numeric, as here, or alphabetic, as here.

            Output should be alphabetic.

Weighted Graph Example

Vertices are labeled with numbers in black.  Weights are marked in blue along the edges.

Sample Input

Human readable:

vertex1    2    3    4    5    6    7    8    9    10   11   12

1    -    23   8    5    -    -    -    -    -    -    -    -

2    23   -    -    -    17   16   -    -    -    -    -    -

3    8    -    -    19   -    -    15   -    -    -    -    -

4    5    -    19   -    -    -    -    11   -    -    -    -

5    -    17   -    -    -    15   -    24   20   -    -    -

6    -    16   -    -    15   -    -    -    14   -    -    21

7    -    -    15   -    -    -    -    25   -    15   -    -

8    -    -    -    11   24   -    25   -    -    9    23   -

9    -    -    -    -    20   14   -    -    -    -    22   -

10   -    -    -    -    -    -    15   9    -    -    6    -

11   -    -    -    -    -    -    -    23   22   6    -    5

12   -    -    -    -    -    21   -    -    -    -    5    -

Per algorithm:

12

∞    23   8    5    ∞    ∞    ∞    ∞    ∞    ∞    ∞    ∞

23   ∞    ∞    ∞    17   16   ∞    ∞    ∞    ∞    ∞    ∞

8    ∞    ∞    19   ∞    ∞    15   ∞    ∞    ∞    ∞    ∞

5    ∞    19   ∞    ∞    ∞    ∞    11   ∞    ∞    ∞    ∞

∞    17   ∞    ∞    ∞    15   ∞    24   20   ∞    ∞    ∞

∞    16   ∞    ∞    15   ∞    ∞    ∞    14   ∞    ∞    21

∞    ∞    15   ∞    ∞    ∞    ∞    25   ∞    15   ∞    ∞

∞    ∞    ∞    11   24   ∞    25   ∞    ∞    9    23   ∞

∞    ∞    ∞    ∞    20   14   ∞    ∞    ∞    ∞    22   ∞

∞    ∞    ∞    ∞    ∞    ∞    15   9    ∞    ∞    6    ∞

∞    ∞    ∞    ∞    ∞    ∞    ∞    23   22   6    ∞    5

∞    ∞    ∞    ∞    ∞    21   ∞    ∞    ∞    ∞    5    ∞

Machine readable:

12

99   23   8    5    99   99   99   99   99   99   99   99

23   99   99   99   17   16   99   99   99   99   99   99

8    99   99   19   99   99   15   99   99   99   99   99

5    99   19   99   99   99   99   11   99   99   99   99

99   17   99   99   99   15   99   24   20   99   99   99

99   16   99   99   15   99   99   99   14   99   99   21

99   99   15   99   99   99   99   25   99   15   99   99

99   99   99   11   24   99   25   99   99   9    23   99

99   99   99   99   20   14   99   99   99   99   22   99

99   99   99   99   99   99   15   9    99   99   6    99

99   99   99   99   99   99   99   23   22   6    99   5

99   99   99   99   99   21   99   99   99   99   5    99