Analysis of Algorithms (AOA)

Single Source Shortest Path in C

Author: Neerav Panchal
/*
	Program for Single Source Shortest Path in C
	Author: Neerav Panchal		Author Link: https://www.facebook.com/neerav.panchal.31
	www.pracspedia.com
*/
#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;
}
Download Source Code Program List

Sample 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