Description:
Given a directed, connected weighted graph G(V,E), for each edge (u,v)€E,
a weight w(u,v) is associated with the edge. The all pairs of shortest paths problem is to find a shortest
path from u to v for every pair
of vertices u and v in V.
Algorithm
- If k=0, then
|
dij (0) ={ 0 if i=j ∞ if i≠j
|
- Otherwise,
for k≥1, dij (k) can be computed
from dij (k-1) and the adjacency matrix w.
dij (k) =min{ dij (k-1) , min1≤l≤n { dil (k-1) + wlj }}= min1≤l≤n { dil (k-1) + wlj }
Solution:
#include<stdio.h>
#include<omp.h>
#include<time.h>
void floyd();
int a[10][10];
void floyd(int
n)
{
int
k,i,j,min;
#pragma omp
parallel for ordered schedule(runtime)
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
}
}
void main()
{
int
i,j,n;
clock_t n1,n2,n3;
float
n4;
omp_set_num_threads(3);
printf("enter the no of
vertices:\n");
scanf("%d",&n);
printf("Give
the weighted adjacency matrices");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
n1=omp_get_wtime();
#pragma
omp parallel
floyd(n);
n2=omp_get_wtime();
n3=n2-n1;
n4=(float)n3/CLOCKS_PER_SEC;
printf("\nMatrix
showing shortest path between all vertices:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%3d",a[i][j]);
printf("\n");
}
printf("\nTime
in microseconds is %f",n4);
}
OUTPUT :
enter the no of vertices:
3
Give the weighted adjacency matrices
0 6 99
99 0 4
3 9 0
Matrix showing shortest path between all vertices:
0 6 10
7 0 4
3 9 0
Time in microseconds is 0.000000
No comments:
Post a Comment