CITS3402 Assignment 2 2019: Shortest Paths
Nicholas Pritchard
September 2019
1 Details
• Due date: Fri 25/10 11:59pm
• Worth: 25%
• You are allowed to undertake this assignment as a pair or individually
The goal of this project is to design an implement parallel algorithms to solve
the all-pairs-shortest path problem for a number of large graphs using either
Dijkstra’s or Floyd-Warshall algorithms. You will use C with the Message-
Passing Interface (MPI) to write parallelized code. You will also need to observe
and comment on how speedup is affected by changing the size of the problem and
the number of nodes you use. A reasonable range for the size of your problems
is 1024 to 4096 vertices. A reasonable range for the number of processors is one
to 16.
Your submission will include:
1.1 Code
A copy of all source files, job scripts and build-files used. Source files must in-
clude your names and student numbers at the top. Your program must compile,
execute correctly and be well documented. Make sure to include comments to
explain any MPI function the first time it is used.
1.2 Report
Alongside your code you will also need to write a report addressing the following
points:
• How your approach partitions data and processing
• A table showing speedup for graphs of 2048 vertices vs 1, 2, 4, 8, 16 pro-
cessors
• A table showing speedup for 4 processors vs graphs of 256, 512, 1024, 2048, 4096
vertices.
1
When discussing the performance of your approach, try to relate performance to
various factors in your computation (number of compute nodes, load balancing,
communication overhead etc.)
2 Code Requirements
File Reading
Your solution should read a matrix description from file. It is acceptable to
implement this with or without flags, for example:
mpirun -n 4 ./my_solution -f file.in
is acceptable as is
mpirun -n 4 ./my_solution file.in
The input file format is essentially a flattened adjacency matrix for a di-
rected, weighted graph. All weights are positive integers. These are binary files
(not text files) and will need to be read in as such. More specifically, each file
contains:
• The number of vertices (numV)
• numV x numV integers specifying the weights for all connections
You can read all the information needed by reading the first integer to determine
how many vertices there are in the graph, then read numV x numV integers into
a freshly allocated array. For example the graph (assuming nodes are labelled
from 0 upwards)
2
corresponds to the following adjacency matrix
0 15 1 1
0 0 3 0
1 3 0 0
0 1 1 0
 (1)
which would be specified by the file example.in
4 0 15 1 1 0 0 3 0 1 3 0 0 0 1 1 0
Being a binary file however, you would not be able to ’read’ the files yourself as
such. We have added an .txt files for all of our example inputs if you would
like to read them yourself to make sure you are correct.
File Writing
The output of either algorithm should be a matrix containing the length of the
shortest path from vertex i to vertex j. This file has the same form as the input
files. That is, a single array length numV*numV + 1 where the first integer is the
number of vertices in the graph. The solution for the example.in file would be
example.out
4 0 2 1 1 4 0 3 5 1 3 0 2 2 1 1 0
You can choose to write this file by default, or enable this feature with command
line arguments. In any case, specify your choice at the top of your code file.
3 Hints
• When timing your program for speedup analysis do not count the time
taken for file operations.
• Passing command line arguments to MPI programs can be a little tricky
compared to standard programs, be careful.
• Dijkstra’s algorithm is made very concise by using a priority queue. Since
C has no default data structure library you are not required to implement
one. A simpler implementation will be accepted.
• A hint for parallelizing Dijkstra’s is that it is a single-source sortest path
algorithm
• A hint for parallelizing the Floyd-Warshall algorithm is that it can be
viewed as iterating over 2D distance matrix.
3
Marking Rubric
Critera Highly
Satisfactory
Satisfactory Unsatisfactory
File Reading (5) Program is able to
read input files as
specified.
Reads in
adjacency files
correctly.
Attempts to read
adjacency files.
No attempt is
made to read
adjacency files.
File Writing (5) Program is able to
write output files
as specified.
Write output files
correctly and
efficiently.
Attempts to write
output files but are
either poorly
formatted or
written
inefficiently.
No attempt is
made to write
output files.
Dijkstra’s
Algorithm or
Floyd Warshall
(60)
Dijkstra’s all-pairs
shortest path or
the Floyd-
Warshall
algorithm is
implemented
correctly in a
parallel fashion.
MPI calls are
explained.
Algorithm is
implemented
correctly and
efficiently.
Comments
indicate an
understanding of
the parallelism
present.
Algorithm is
either incorrect for
some cases or
inefficient.
Parallelism is
attempted but not
efficiently.
Algorithm is
implemented
incorrectly for all
cases or missing.
Parallelism is not
attempted.
Report (30) Addresses all
required points
and is presented
clearly. Testing is
thorough and
clear.
Report addresses
all points
effectively and is
presented clearly.
Performance
testing is thorough
and meaningful.
Report does not
address all points
required or some
minor readiblity
issues.
Report addresses
few points or is
very difficult to
read.
A Graphs
Graphs and graph theory provides a natural way to model many problems.
Power-grids, transport systems, social structures and nervous systems can all be
modelled by large graphs for example. For completeness we provide a definition
of a graph below:
• A graph G is specified by two sets V and E
• V is a finite set of points called vertices
• E is a finite set of edges
• An edge e is an ordered pair of two vertices (u, v) indicating that vertex
u is connected to vertex v.
• Edges can be weighted or un-weighted. For our assignment, edges are
weighted by positive integers. This forms an extra set of weights w to go
along with our vertices and edges.
• Graphs can be directed or un-directed (for every (u, v) there exists an edge
(v, u))
• Vertices u and v are adjacent to each other if there is an edge (u, v) or
(v, u) present
• A path from vertex u to vertex v is a sequence of vertices following edges
that exist in our graph.
• The shortest-path from vertex u to vertex v in a weighted graph is a
path with minimum sum-weight
B All-Pairs Shortest Paths
For a weighted graph, the all-pairs shortest paths problem is to find the
shortest path between all pairs of vertices.
C Dijkstra’s Algorithm
Dijkstra’s algorithm finds the shortest paths from a starting vertex s to all
other vertices in the graph. It incrementally selects edges that appear closest
to a vertex to build a set of paths, updating the length of a path if a superior
option is found. For more reading, you can start with 1, 2 or 3. An all-pairs
shortest path implementation is found by running Dijkstra’s for each possible
source.
5
D Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is an all-pairs shortest path algorithm which con-
siders the shortest paths possible over zero ’hops’ upwards. Trivially a path of
a single hop is the adjacency of all vertices. The computation of all subsequent
paths is based on the following observation.
For three vertices i, j, k the shortest path from i to j either includes the
paths i to k plus k to j or it does not. This boils down to exceedingly concise
pseudo-code. For more reading consult 1 2 3
6