Code Scrappers


Dijikstra Algorithm - C Program


                    #include<stdio.h>
                    #include<stdlib.h>

                    void main()

                    {
                            int i, j, n, startn, nextn, count, minc, mindistance;

                            int c[10][10], dist[10], visit[10], pre[10];

                            printf("enter the no. of vertices\n");

                            scanf("%d",&n);

                            printf("enter the matrix\n");

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

                            {
                                    for(j=0;j<n;j++)
                                    {
                                            scanf("%d",&c[i][j]);

                                            if(c[i][j] == 0)
                                            {
                                                    c[i][j] = 9999;
                                            }

                                    }
                            }

                            printf("enter the startnode\n");

                            scanf("%d",&startn);



                            for(i=0;i<n;i++)
                            {
                                    dist[i] = c[startn][i];

                                    visit[i] = 0;

                                    pre[i] = startn;
                            }

                            count = 1;

                            dist[startn] = 0;

                            visit[startn] = 1;

                            while(count < n)

                            {
                                    mindistance = 9999;

                                    for(i=0;i<n;i++)
                                    {
                                            if(dist[i] < mindistance && !visit[i])
                                            {
                                                    mindistance = dist[i];

                                                    nextn = i;
                                            }
                                    }

                                    visit[nextn] = 1;

                                    for(i=0;i<n;i++)
                                    {
                                            if(!visit[i])
                                            {
                                                    if(mindistance + c[nextn][i] < dist[i])
                                                    {
                                                            dist[i] = mindistance + c[nextn][i];

                                                            pre[i] = nextn;
                                                    }
                                            }
                                    }

                                    count++;
                            }

                            for(i=0;i<n;i++)
                            {
                                    if(i!=startn)
                                    {
                                            printf("\ndistance of %d is %d\n", i, dist[i]);

                                            printf("path = %d",i);

                                             j = i;

                                            do
                                            {
                                                    j = pre[j];

                                                    printf("<-- %d",j);
                                            }
                                            while(j!=startn);
                                    }
                            }
                    }


                



Output

              enter the no. of vertices
              4

              enter the matrix
              0
              10
              0
              2
              10
              0
              6
              0
              0
              6
              0
              8
              2
              0
              8
              0

              enter the startnode
              0

              distance of 1 is 10

              path = 1<-- 0

              distance of 2 is 10

              path = 2<-- 3<-- 0

              distance of 3 is 2

              path = 3<-- 0