#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define infinity 9999
#define MAX 1000
int G[MAX][MAX],spanning[MAX][MAX],n;
void random1(int n)
{
int i,j;
FILE *fp;
fp=fopen("number.txt","w");
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
fprintf(fp,"%d ",rand()%n);
}
}
fclose(fp);
}
int djikstra();
int main()
{
int i, j, total_cost;
FILE *fp ;
clock_t t1;
double time;
printf("Enter no. of vertices:");
scanf("%d", &n);
random1(n);
fp=fopen("number.txt","r");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
fscanf(fp,"%d", &G[i][j]);
}
}
fclose(fp);
//printf("\nEnter the adjacency matrix:\n");
/*for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &G[i][j]);
total_cost = djikstra();
printf("\nspanning tree matrix:\n");
for(i = 0; i < n; i++)
{
printf("\n");
for(j = 0; j < n; j++)
printf("%d\t", spanning[i][j]);
}*/
t1=clock();
total_cost = djikstra();
t1=clock()-t1;
time=(double)t1/CLOCKS_PER_SEC;
printf("%f",time);
//printf("\n\nTotal cost of spanning tree=%d", total_cost);
return 0;
}
int djikstra()
{
int cost[MAX][MAX];
int u, v, min_distance, distance[MAX], from[MAX];
int visited[MAX], no_of_edges, i, min_cost, j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
if(G[i][j] == 0)
cost[i][j] = infinity;
else
cost[i][j] = G[i][j];
spanning[i][j] = 0;
}
distance[0] = 0;
visited[0] = 1;
for(i = 1; i < n; i++)
{
distance[i] = cost[0][i];
from[i] = 0;
visited[i] = 0;
}
min_cost = 0;
no_of_edges = n - 1;
while(no_of_edges > 0)
{
min_distance = infinity;
for(i = 1; i < n; i++)
if(visited[i] == 0&&distance[i] < min_distance)
{
v = i;
min_distance = distance[i];
}
u=from[v];
spanning[u][v] = distance[v];
spanning[v][u] = distance[v];
no_of_edges--;
visited[v] = 1;
for(i = 1; i < n; i++)
if(visited[i] == 0 && cost[i][v] < distance[i])
{
distance[i] = cost[i][v];
from[i] = v;
}
min_cost = min_cost + cost[u][v];
}
return(min_cost);
}
