Implement Floyd-Warshall (FW) All-Pairs-Shortest-Path algorithm in a multi-threaded fashion along with enforcing the readers-writers problem in C program.

Multi threaded Implementation: In the multi threaded implementation of FW, the k loop remains same. Instead of the i loop, we create n threads that represent each iteration of the i loop. Each thread runs the j loop from 1 to n. There is a global matrix Graph that stores the adjacency matrix for the graph. All the threads can read it simultaneously. There is another global matrix dist that is used for updating the minimum distances between the vertices. Only 1 copy of dist will suffice. At the start of every iteration inside the k loop, you need to create n threads. Each thread will run its own j loop. You have to enforce readers-writers problem in the manner of how the dist matrix is accessed by the different threads. Any number of threads can read from the dist matrix provided that no other thread is writing to it. Only 1 thread can write to the dist matrix at a time. If you observe closely, line 4 has only read statements and line 5 is the only write statement present in the algorithm. Hence, these two lines need appropriate synchronization. At the end of every iteration of the k loop, you need to wait for all the threads to finish. Then only can you start another iteration of the k loop. You have to join the threads at the end of every iteration of the k loop. Analysis: Implement the single threaded and multi-threaded versions of Floyd-Warshall algorithm. Run the algorithm for graphs of different sizes, e.g., 10, 100, 1000, 10000 and observe the speed up improvement. Do you find any limit on the number of threads that can be created on your system? Compute the speed up (time taken by single threaded version/time taken by multi threaded version) obtained through multi threading and include the graph plot in your final report with relevant inferences. Note that the to get the real speed up, you have to perform this experiment on a multi core system. Most of the modern computers are multi-core today and can actually run several threads concurrently. Report the system architecture on which you performed the experiment, e.g., processor type and clock rate, # cores, RAM etc... Input Format: Graph structure: The first line contains 2 integers N and M. N is the number of nodes. M is the number of undirected edges. Then each entry contains the link information (M entries). Line i+1 contains 3 integers ui, vi and wi which represents an undirected edge between nodes ui, vi and wi is the weight of that edge. Use positive edge weights. Your program should inform the user if he/she unknowingly provide a negative edge weight. Output Format: Print the final dist matrix. In case node j is not reachable from node i, then print INF as the distance between i and j.

Sample input and output: Input 4 4 1 2 1 2 3 1 3 4 1 4 1 1 Output: 0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0

Here is the code for only single thread:

// C Program for Floyd Warshall Algorithm

#include

// Number of vertices in the graph

#define V 4

/* Define Infinite as a large enough value. This value will be used

for vertices not connected to each other */

#define INF 99999

// A function to print the solution matrix

void printSolution(int dist[][V]);

// Solves the all-pairs shortest path problem using Floyd Warshall algorithm

void floydWarshall (int graph[][V])

{

/* dist[][] will be the output matrix that will finally have the shortest

distances between every pair of vertices */

int dist[V][V], i, j, k;

/* Initialize the solution matrix same as input graph matrix. Or

we can say the initial values of shortest distances are based

on shortest paths considering no intermediate vertex. */

for (i = 0; i < V; i++)

for (j = 0; j < V; j++)

dist[i][j] = graph[i][j];

/* Add all vertices one by one to the set of intermediate vertices.

---> Before start of an iteration, we have shortest distances between all

pairs of vertices such that the shortest distances consider only the

vertices in set {0, 1, 2, .. k-1} as intermediate vertices.

----> After the end of an iteration, vertex no. k is added to the set of

intermediate vertices and the set becomes {0, 1, 2, .. k} */

for (k = 0; k < V; k++)

{

// Pick all vertices as source one by one

for (i = 0; i < V; i++)

{

// Pick all vertices as destination for the

// above picked source

for (j = 0; j < V; j++)

{

// If vertex k is on the shortest path from

// i to j, then update the value of dist[i][j]

if (dist[i][k] + dist[k][j] < dist[i][j])

dist[i][j] = dist[i][k] + dist[k][j];

}

}

}

// Print the shortest distance matrix

printSolution(dist);

}

/* A utility function to print solution */

void printSolution(int dist[][V])

{

printf ("The following matrix shows the shortest distances"

" between every pair of vertices ");

for (int i = 0; i < V; i++)

{

for (int j = 0; j < V; j++)

{

if (dist[i][j] == INF)

printf("%7s", "INF");

else

printf ("%7d", dist[i][j]);

}

printf(" ");

}

}