The idea is simple: given a directed graph G = (V,E) in which V is the set of nodes (or vertices) and E is the set of links (or edges) between nodes, the goal is to determine for each pair of nodes (vi,vj) the size of the shortest path that begins in vi and ends in vj. A path is simply a sequence of links in which the end node and start node of two consecutive links are the same. One link can be seen as a tuple of the form <vi, vj, t> where vi is the origin node, vj is the destination node and t is the size of the link between the nodes. The sum of the sizes of the links is the size of the path between vi and vj.

A well-known algorithm to efficiently compute the multiplication of matrices with the same size in distributed environments is Fox's algorithm. The application of Fox's algorithm is not always possible, it depends on the dimension of the matrices being multiplied and on the available processes. Given matrices of size NxN and P processors, there must exist an integer Q such that P = Q*Q and N mod Q = 0, otherwise the algorithm cannot be applied. Fox's algorithm then divides the NxN matrices into sub-matrices with dimension (N/Q)x(N/Q) and assigns each one to the P processors available in the system.

To compute the result of each sub-matrix multiplication, each process only needs to exchange information with the processes in the same row and same column of its sub-matrix, thus reducing the number of messages that need to be exchanged (see pages 29 and 30 of the6 0 2 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 5 0 0 0 0 1 0 3 9 3 0 0 0 0 0 0 0 1 0If the dimension of the matrix and the number of available processes are not compatible with the conditions of the Fox algorithm, you must provide an appropriate error message and the execution must be canceled.

As output, your application must print the Df matrix representing the solution for the problem, one row per line. For the given example, the output should be:

0 2 9 5 6 14 0 0 0 0 0 0 9 2 0 14 6 5 4 6 4 0 1 9 3 5 3 8 0 8 4 6 4 9 1 0The input file must be read from the standard input and the results are to be printed to the standard output (click

- All source code files (can be just one) implementing your solution
- A makefile that generates the executable program (assign name fox)
- Short technical report (no more than 5 pages) in PDF format
describing the work done (free structure) and including:
- A summary on the algorithm implementation (include details about the base idea of the algorithm, main data structures, relevant auxiliary functions, type of communications, ...)
- Performance evaluation including execution times (in milliseconds and excluding I/O) and speedups (comparing with sequential execution and with execution with 1 process) for, at least, 1, 4, 9 and 16 processes
- Main difficulties encountered in the development of the work (if any) and comments/suggestions about the work (optional)

- Generate an authentication key with the command
`ssh-keygen -t rsa`This will produce two files in your home directory:

`~/.ssh/id_rsa`with your private key, and`~/.ssh/id_rsa.pub`with your public key - Copy your public key to the
`authorization_keys`file with the command:`cp ~/.ssh/id_rsa.pub ~/.ssh/authorized_keys` - Try it! The command
`ssh node_xpto`should now log you in at

`node_xpto`without needing to type in the password