Trend Posts
Author
View LUQMAN's profile
Showing posts with label shortest path. Show all posts
Showing posts with label shortest path. Show all posts
Monday, July 21, 2014
/* Implement All-Pairs Shortest Paths Problem using Floyd's algorithm. Parallelize this algorithm, implement it using OpenMP and determine the speed-up achieved.*/
#include<stdio.h>
#include<omp.h>
#include<time.h>
void floyds(int);
int min(int,int);
int cost[10][10],n,i,j,k,a,b;
double start,end,dur;
void main()
{
printf("Enter the number of nodes\n\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\n\nThe cost matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
start=clock();
for(i=1;i<=100000;i++)
floyds(n);
end=clock();
dur=(end-start)/CLOCKS_PER_SEC;
printf("\nTime taken is:%f\t\n",dur);
printf("\nThe minimum cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
}
void floyds(int n)
{
omp_set_num_threads(4);
#pragma omp parallel for private(i,j,k)
for(k=1;k<=n;k++)
{
usleep(100);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
}
}
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
Subscribe to:
Posts (Atom)