Spooky Wall-Guy

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.