Description
Part A:
1. Implement Floyd’s Algorithm for all pairs shortest paths using C or C++ or Java. (50 pts)
ALGORITHM Floyd(W[1, . . . , n, 1, . . . , n])
D ← W
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
D[i, j] ← min{D[i, j], D[i, k] + D[k, j]}
return D
Requirements:
(a) Your code should be able to read an input ASCII file named ‘input.txt’, which contains a distance
matrix with non-negative floating-number distances and the diagonal entries are all zeros.
(b) Your code will produce an output ASCII file named ‘output.txt’, which contains the final distance
matrix for all pairs shortest paths.
(c) A script file or readme file including the instructions to compile and run the code should be
submitted together with the codes
2. Implement the M aximumBipartiteM atching(G) in Section 10.3 in your text book in C or C + +
or Java. (100 pts)
Requirements:
(a) Your code should be able to read an input ASCII file named ‘input.txt’, which contains the
vertices from set V in the first row in the form of an array separated by space, the vertices from
set V in the first row in the form of an array separated by space, and starting from third row, the
adjacency matrix is stored as a two-dimensional array.
(b) Your code will produce an output ASCII file named ‘output.txt’ containing the maximum matching of the input bipartite graph in the same format as the input.
(c) A script file or readme file including the instructions to compile and run the code should be
submitted together with the codes
1
