#include<stdio.h>
#include<limits.h>
typedef enum {false, true} bool;
void dijkstra_algo(int g_raph[9][9], int source, int vertices_Count);
int minimum_distance(int d_istance[40],bool shortest_path_tree_set[9], int vertices_Count);
void p_rint(int d_istance[40], int vertices_Count);
int main( )
{
int grd[9][9]= {
{1,6,10,20,2,30,40,19,50},
{3,40,4,20,50,4,20,1,60},
{40,67,40,12,10,23,30,20,56},
{10,60,25,30,19,116,70,80,90},
{40,30,20,29,10,10,40,50,70},
{20,40,62,60,120,50,22,21,80},
{40,40,50,116,20,32,40,21,16},
{59,141,60,20,60,20,171,50,85},
{60,80,32,40,60,70,64,75,40}
};
digikstra_algo(g_raph,0,9);
return 0;
}
int minimum_distance(int d_istance[40], bool shortest_path_tree_set[9], int vertice_Count)
{
int v;
int min = INT_MAX;
int min_Index = 0;
for(v=0;v<vertice_Count;++v)
{
if (shortest_path_tree_set[v]==false && d_istance[v]<=min)
{
min = d_istance[v];
min_Index = v;
}
}
return min_Index;
}
void p_rint(int d_istance[ ], int vertices_Count)
{
int i;
printf(“Distance of Vertex from source is: \n”);
for(i=0;i<vertices_Count;++i)
{
printf(“%d \t %d \n”,i, d_istance[i]);
}
}
void dijkstra_algo(int g_raph[9][9], int source, int vertices_Count)
{
int count,v,i,j;
int d_istance[40];
bool shortest_path_tree_set[9];
for(i=0;i<vertices_Count;i++)
{
d_istance[i]=INT_MAX;
shortest_path_tree_set[i]=false;
}
d_istance[source]=0;
for(count=0;count<vertices_Count-1;++count)
{
int u = minimum_distance(d_istance, shortest_path_tree_set, vertices_Count);
printf(“Minimum Distance value is %d\n”,u);
shortest_path_tree_set[u] = true;
for(v=0;v<vertices_Count;++v)
{
printf(“\n”);
printf(“the value of v %d”, v);
printf(“\n”);
if(!shortest_path_tree_set[v])
{
printf(“I am in !shortest_path_tree_set[v] if statement \n”);
if(d_istance[u]!=INT_MAX)
{
printf(“I am in d_istance[u]!=INT_MAX if statement \n”);
printf(“%d \n”, g_raph[u][v]);
printf(“d_istance[v] %d \n”, d_istance[v]);
printf(“d_istance[source] %d \n”, d_istance[source]);
printf(“d_istance[u] %d \n”, d_istance[u]);
printf(“d_istance[u]+g_raph[u][v] %d \n”, d_istance[u]+g_raph[u][v]);
if( d_istance[u]+g_raph[u][v] < d_istance[v] )
{
printf(“I am in d_istance[u]+graph[u][v]<d_istance[v] If statement \n”);
d_istance[v]=d_istance[u]+g_raph[u][v];
printf(“d_istance[v] %d \n”, d_istance[v]);
}
}
}
}
p_rint(d_istance,vertices_Count);
}
Output: Minimum Distance value is 0 the value of v 0 the value of v 1 I am in !shortest_Path_Tree_Set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 6 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 6 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 6 the value of v 2 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 10 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 10 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 10 the value of v 3 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 20 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 20 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 20 the value of v 4 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 2 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 2 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 2 the value of v 5 I am in !shortest_path_tree_Set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 30 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 30 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 30 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 40 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 40 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 40 the value of v 7 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 19 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 19 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 19 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 50 d_istance[v] 2147483647 d_istance[source] 0 d_istance[u] 0 d_istance[u]+g_raph[u][v] 50 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 50 Vertex Distance from source: 0 0 1 6 2 10 3 20 4 2 5 30 6 40 7 19 8 50 Minimum Distance value is 4 the value of v 0 the value of v 1 I am in !shortest_path_tree_Set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 30 d_istance[v] 6 d_istance[source] 0 d_istance[u] 2 d_istance[u]+g_raph[u][v] 32 the value of v 2 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 0 d_istance[v] 10 d_istance[source] 0 d_istance[u] 2 d_istance[u]+g_raph[u][v] 22 the value of v 3 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 29 d_istance[v] 20 d_istance[source] 0 d_istance[u] 2 d_istance[u]+g_raph[u][v] 31 the value of v 4 the value of v 5 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 10 d_istance[v] 30 d_istance[source] 0 d_istance[u] 2 d_istance[u]+graph[u][v] 12 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 12 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 40 d_istance[v] 40 d_istance[source] 0 d_istance[u] 2 d_istance[u]+g_raph[u][v] 42 the value of v 7 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 50 d_istance[v] 19 d_istance[source] 0 d_istance[u] 2 d_istance[u]+g_raph[u][v] 52 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 70 d_istance[v] 50 d_istance[source] 0 d_istance[u] 2 d_istance[u]+graph[u][v] 72 Vertex Distance from source: 0 0 1 6 2 10 3 20 4 2 5 12 6 40 7 19 8 50 Minimum Distance value is 1 the value of v 0 the value of v 1 the value of v 2 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 4 d_istance[v] 10 d_istance[source] 0 d_istance[u] 6 d_istance[u]+g_raph[u][v] 10 the value of v 3 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 20 d_istance[v] 20 d_istance[source] 0 d_istance[u] 6 d_istance[u]+g_raph[u][v] 26 the value of v 4 the value of v 5 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 4 d_istance[v] 12 d_istance[source] 0 d_istance[u] 6 d_istance[u]+g_raph[u][v] 10 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 10 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 20 d_istance[v] 40 d_istance[source] 0 d_istance[u] 6 d_istance[u]+graph[u][v] 26 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 26 the value of v 7 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 1 d_istance[v] 19 d_istance[source] 0 d_istance[u] 6 d_istance[u]+g_raph[u][v] 7 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 7 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 60 d_istance[v] 50 d_istance[source] 0 d_istance[u] 6 d_istance[u]+g_raph[u][v] 66 Vertex Distance from source: 0 0 1 6 2 10 3 20 4 2 5 10 6 26 7 7 8 50 Minimum Distance value is 7 the value of v 0 the value of v 1 the value of v 2 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 60 d_istance[v] 10 d_istance[source] 0 d_istance[u] 7 d_istance[u]+g_raph[u][v] 67 the value of v 3 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 20 d_istance[v] 20 d_istance[source] 0 d_istance[u] 7 d_istance[u]+g_raph[u][v] 27 the value of v 4 the value of v 5 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 20 d_istance[v] 10 d_istance[source] 0 d_istance[u] 7 d_istance[u]+g_raph[u][v] 27 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 71 d_istance[v] 26 d_istance[source] 0 d_istance[u] 7 d_istance[u]+g_raph[u][v] 78 the value of v 7 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 85 d_istance[v] 50 d_istance[source] 0 d_istance[u] 7 d_istance[u]+g_raph[u][v] 92 Distance of Vertex from source is: 0 0 1 6 2 10 3 20 4 2 5 10 6 26 7 7 8 50 Minimum Distance value is 5 the value of v 0 the value of v 1 the value of v 2 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 62 d_istance[v] 10 d_istance[source] 0 d_istance[u] 10 d_istance[u]+g_raph[u][v] 72 the value of v 3 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 60 d_istance[v] 20 d_istance[source] 0 d_istance[u] 10 d_istance[u]+graph[u][v] 70 the value of v 4 the value of v 5 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 22 d_istance[v] 26 d_istance[source] 0 d_istance[u] 10 d_istance[u]+g_raph[u][v] 32 the value of v 7 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 80 d_istance[v] 50 d_istance[source] 0 d_istance[u] 10 d_istance[u]+g_raph[u][v] 90 Distance of Vertex from source is: 0 0 1 6 2 10 3 20 4 2 5 10 6 26 7 7 8 50 Minimum Distance value is 2 the value of v 0 the value of v 1 the value of v 2 the value of v 3 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 12 d_istance[v] 20 d_istance[source] 0 d_istance[u] 10 d_istance[u]+g_raph[u][v] 22 the value of v 4 the value of v 5 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 30 d_istance[v] 26 d_istance[source] 0 distance[u] 10 d_istance[u]+g_raph[u][v] 40 the value of v 7 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 56 d_istance[v] 50 d_istance[source] 0 d_istance[u] 10 d_istance[u]+g_raph[u][v] 66 Distance of Vertex from source: 0 0 1 6 2 10 3 20 4 2 5 10 6 26 7 7 8 50 Minimum Distance value is 3 the value of v 0 the value of v 1 the value of v 2 the value of v 3 the value of v 4 the value of v 5 the value of v 6 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 0 d_istance[v] 26 d_istance[source] 0 d_istance[u] 20 d_istance[u]+g_raph[u][v] 90 the value of v 7 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 90 d_istance[v] 50 d_istance[source] 0 d_istance[u] 20 d_istance[u]+g_raph[u][v] 110 Vertex Distance from source: 0 0 1 6 2 10 3 20 4 2 5 10 6 26 7 7 8 50 Minimum Distance value is 6 the value of v 0 the value of v 1 the value of v 2 the value of v 3 the value of v 4 the value of v 5 the value of v 6 the value of v 7 the value of v 8 I am in !shortest_path_tree_set[v] If statement I am in (bool)g_raph[u,v] If statement I am in d_istance[u]!=INT_MAX If statement 16 d_istance[v] 50 d_istance[source] 0 d_istance[u] 26 d_istance[u]+graph[u][v] 42 I am in d_istance[u]+g_raph[u,v] < d_istance[v] If statement d_istance[v] 42 Distance of vertex from source is: 0 0 1 6 2 10 3 20 4 2 5 10 6 26 7 7 8 42
