Write a program to find the single source shortest path.

Name of the experiment:  Write a program to find the single source shortest path.

Algorithm:

1       Algorithm  ShortestPaths( v, cost, dist, n)

2       {

3                 for i:= 1 to n  do

4                 {

5                           S[i]:= false; dist [i]:= cost [v, i];

6                 }

7                 S[v]:= true;  dist[v]:=0.0;

8                 for num:= 2  to  n-1   do

9                 {

10               Choose u from among those vertices not

11               in S such that dist[u] is minimum;

12               S[u]:= true;

13               for 9each w adjacent to u with s[w] = false0  do

14                        if (dist[w] > dist [u] + cost[u,w])) then

15                                  dist[w]:= dist[u] + cost[u,w];

16               }

17     }

Source Code:

#include<stdio.h>

#include<conio.h>

int cost[8][8],dist[8][8],n;

void main()

{

            int i,j,k,m,u,INF=100;

            printf("\nEnter the no. of vertices: ");

            scanf("%d",&n);

            printf("\nEnter the adjacency matrix(Enter 100 if there is no edge present)\n");

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

                        for(j=1;j <= n;j++)

                        {

                                    scanf("%d",&cost[i][j]);

                        }

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

                        dist[i][1]=0;

            printf("\nDistance Matrix:\n");

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

            {

                        dist[1][i]=cost[1][i];

                        printf("%d    ",dist[1][i]);

            }

            printf("\n");

            printf("\n");

            for(k=2;k < n;k++)

            {

                        for(u=2;u <= n;u++)

                        {

                                    m=min(k,u);

                                    if(dist[k-1][u] > m)

                                                dist[k][u]=m;

                                    else

                                                dist[k][u]=dist[k-1][u];

                                    printf("%d    ",dist[k][u]);

                        }

                        printf("\n");

                        printf("\n");

            }

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

            {

                        printf("\nDistance of 1 to %d is ",i);

                        printf("%d    ",dist[n-1][i]);

            }

            getch();

}

int min(int k,int u)

{

            int min1,i;

            min1=dist[k-1][1]+cost[1][u];

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

                        if(min1 > (dist[k-1][i]+cost[i][u]))

                                    min1=dist[k-1][i]+cost[i][u];

            return min1;

}

Sample Input and Output:

Enter the no. of vertices:                7

Enter the adjacency matrix (Enter 100 if there is no edge present)

0          6          5          5          100     100     100

100     0          100     100     -1        100     100    

100     -2        0          100     1          100     100

100     100     -2        0          100     -1        100

100     100     100     100     0          100     3

100     100     100     100     100     0          3

100     100     100     100     100     100     0

Distance Matrix:

6          5          5          100     100     100

3          3          5          5          4          100

1          3          5          2          4          7

1          3          5          0          4          5

1          3          5          0          4          3

1          3          5          0          4          3

Distance of 1 to 1 is 0

Distance of 1 to 2 is 1

Distance of 1 to 3 is 3

Distance of 1 to 4 is 5

Distance of 1 to 5 is 0

Distance of 1 to 6 is 4

Distance of 1 to 7 is 3