All Pair Shortest Path

#include<stdio.h>

int min(int,int);

void allpair(int p[10][10],int n)
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j)
                    p[i][j]=0;
                else
                    p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}

int min(int a,int b)
{
    if(a<b)
        return(a);
    else
        return(b);
}
void main()
{
    int p[10][10],w,n,e,u,v,i,j;;
    printf("Enter the number of vertices: ");
    scanf("%d",&n);
    printf("Enter the number of edges: ");
    scanf("%d",&e);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            p[i][j]=999;
    }
    for(i=1;i<=e;i++)
    {
        printf("Enter the end vertices of edge %d with its weight \n",i);
        scanf("%d%d%d",&u,&v,&w);
        p[u][v]=w;
    }
    printf("\nMatrix of input data:\n");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            printf("%d \t",p[i][j]);
        printf("\n");
    }
    allpair(p,n);
    printf("\nTransitive closure:\n");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            printf("%d ",p[i][j]);
        printf("\n");
    }
    printf("\nThe shortest paths are:\n");
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(i!=j)
                printf("From %d to %d = %d\n",i,j,p[i][j]);
        }
}

/*OUTPUT:
Enter the number of vertices: 3
Enter the number of edges: 5
Enter the end vertices of edge 1 with its weight
1 2 4
Enter the end vertices of edge 2 with its weight
1 3 11
Enter the end vertices of edge 3 with its weight
2 1 6
Enter the end vertices of edge 4 with its weight
2 3 2
Enter the end vertices of edge 5 with its weight
3 1 3

Matrix of input data:
999 4 11
6 999 2
3 999 999

Transitive closure:
0 4 6
5 0 2
3 7 0

The shortest paths are:
From 1 to 2 = 4
From 1 to 3 = 6
From 2 to 1 = 5
From 2 to 3 = 2
From 3 to 1 = 3
From 3 to 2 = 7
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s