14 April, 2012

dijktras.......


#include<stdio.h>
int **cost,n,*parent,v,*s;
void dijk(int []);
int min(int []);
int main()
{
        int i,j;
        system("clear");
        printf("Enter no.of vertices in graph\n");
        scanf("%d",&n);
        cost=(int **)malloc(n*sizeof(int *));
        for(i=0;i<n;i++)
        cost[i]=(int *)malloc(n*sizeof(int));
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        printf("Enter distance between %d and %d\n",i+1,j+1);
                        scanf("%d",&cost[i][j]);
                }
        }
        int *dist=(int *)malloc(n*sizeof(int));
        s=(int *)malloc(n*sizeof(int));
        parent=(int *)malloc(n*sizeof(int));
        printf("Enter starting vertex\n");
        scanf("%d",&j);
        v=j-1;
        dijk(dist);
}
int min(int a[])
{
        int temp=10000,i,j;
        for(i=0;i<n;i++)
        {
                if(a[i]==0)
                continue;
                else if(a[i]<temp&&s[i]!=1)
                {
                        temp=a[i];
                        j=i;
                }
        }
        return j;
}

void dijk(int dist[])
{
        int i,num,j;
        for(i=0;i<n;i++)
        {
                s[i]=0;
                dist[i]=cost[v][i];
                if(dist[i]!=1000)
                parent[i]=v+1;
                else
                parent[i]=1000;
        }
        int ver;
        s[v]=1;
        dist[v]=0;
        for(num=2;num<=n;num++)
        {
                ver=min(dist);
                s[ver]=1;
                for(i=0;i<n;i++)
                {
                        if(s[i]==0&&(dist[i]>(dist[ver]+cost[ver][i])))
                        {
                                dist[i]=dist[ver]+cost[ver][i];
                                parent[i]=ver+1;
                        }
                }
        }
        printf("Paths\n");
        printf("PATH\tCOST\n");
        for(i=0;i<n;i++)
        {
                if(parent[i]==v+1)
                printf("%d\t%d\n",parent[i],dist[i]);
                else if(parent[i]!=1000)
                {
                        printf("%d ",parent[i]);
                        j=parent[i]-1;
                        while(parent[j]!=v+1)
                        {
                                printf("<- %d ",parent[i]);
                                j=parent[j]-1;
                        }
                        printf("<- %d\t%d\n",parent[i],dist[i]);
                }
                else
                printf("%d node cannot be reachedi\n",i+1);
        }
}

No comments:

Post a Comment