** CSC 726, Parallel Algorithms **

** Floyd-Warshall Shortest Path**

This page contains a list of examples and helpful code
fragments for running your parallel (MPI) shortest path
code. All binary files are in a simple format. A file
begins with
two 4-byte little-endian binary integers: **m** and **n**.
Those two integers are followed by **mn** 4-byte little-endian
binary integers, representing a weighted adjacency matrix. In all
of our examples, it will always be the case that **m = n**,
i.e., our adjacency matrices, representing a graph are always
square.

When an edge between node **x** and node **y** does not exist
in the graph, the edge weight is considered to be **infinity**.
Infinite weights are represented by **-1** in the input and output data.

Sample code to read this data format is given in the two
files io_idat.h and io_idat.c

** A Small Sample Problem**
Here is a small 8 x 8 problem: Graph8.idat
The same data is available as a text file for visual confirmation:
Graph8.txt. The shortest path matrix
(to help you check your answers) is given in binary form by
Short8.idat and in text form by
Short8.txt.

** A Medium-Large Sample Problem**
Here is a medium-large 3000 x 3000 problem:
Graph3000.idat
The shortest path matrix
(to help you check your answers) is given in binary form by
Short3000.idat.

** A Large Sample Problem**
** (use this one for final timing runs) **
Here is a large 4000 x 4000 problem: Graph4000.idat
The shortest path matrix
(to help you check your answers) is given in binary form by
Short4000.idat.