Dijkstra Program In C

```#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
```