# C Program to find Shortest Distances or Path using Dijkstra’s algorithm

By | 02.07.2017

## Shortest Distances or Path using Dijkstra’s algorithm

Write a C Program to find Shortest Distances or Path using Dijkstra’s algorithm with Output. Here’s a simple Program to find Shortest Path or Distances using Dijkstra’s algorithm with output in C Programming Language.

### Dijkstra’s Algorithm

Dijkstra’s algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm Steps:

• Set all vertices distances = infinity except for the source vertex, set the source distance = .
• Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.
• Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
• Update the distances of the connected vertices to the popped vertex in case of “current vertex distance + edge weight < next vertex distance”, then push the vertex
with the new distance to the priority queue.
• If the popped vertex is visited before, just continue without using it.
• Apply the same algorithm again until the priority queue is empty.

Time Complexity:

• The time complexity of the above code/algorithm looks O(V^2) as there are two nested while loops. If we take a closer look, we can observe that the statements in inner loop are executed O(V+E) times (similar to BFS).
• The inner loop has decreaseKey() operation which takes O(LogV) time. So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV)

Also Read : : C Program to find whether an Undirected Graph is Cyclic or not

Below is the source code for C Program to find Shortest Distances or Path using Dijkstra’s algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :

### SOURCE CODE : :

```/* C Program to find Shortest Distances or Path using Dijkstra's algorithm */

#include<stdio.h>

#define MAX 100
#define TEMP 0
#define PERM 1
#define infinity 9999
#define NIL -1

void findPath(int s, int v );
void Dijkstra( int s);
int min_temp( );
void create_graph();

int n;    /* Denotes number of vertices in the graph */
int predecessor[MAX];   /*predecessor of each vertex in shortest path*/
int pathLength[MAX];
int status[MAX];

int main()
{
int s,v;

create_graph();

printf("\nEnter source vertex : ");
scanf("%d",&s);

Dijkstra(s);

while(1)
{
printf("\nEnter destination vertex(-1 to quit): ");
scanf("%d",&v);
if(v == -1)
break;
if(v < 0 || v >= n )
printf("\nThis vertex does not exist\n");
else if(v == s)
printf("\nSource and destination vertices are same\n");
else if( pathLength[v] == infinity )
printf("\nThere is no path from source to destination vertex\n");
else
findPath(s,v);
}

return 0;
}/*End of main()*/

void Dijkstra( int s)
{
int i,current;

/* Make all vertices temporary */
for(i=0; i<n; i++)
{
predecessor[i] =  NIL;
pathLength[i] = infinity;
status[i] = TEMP;
}
/* Make pathLength of source vertex equal to 0 */
pathLength[s] = 0;

while(1)
{
/*Search for temporary vertex with minimum pathLength
and make it current vertex*/
current = min_temp( );

if( current == NIL )
return;

status[current] = PERM;

for(i=0; i<n; i++)
{
/*Checks for adjacent temporary vertices */
if ( adj[current][i] !=0 && status[i] == TEMP )
if( pathLength[current] + adj[current][i] < pathLength[i] )
{
predecessor[i] = current;  /*Relabel*/
}
}
}
}/*End of Dijkstra( )*/

/*Returns the temporary vertex with minimum value of pathLength
Returns NIL if no temporary vertex left or
all temporary vertices left have pathLength infinity*/
int min_temp( )
{
int i;
int min = infinity;
int k = NIL;
for(i=0;i<n;i++)
{
if(status[i] == TEMP && pathLength[i] < min)
{
min = pathLength[i];
k = i;
}
}
return k;
}/*End of min_temp( )*/

void findPath(int s, int v )
{
int i,u;
int path[MAX];          /*stores the shortest path*/
int shortdist = 0;      /*length of shortest path*/
int count = 0;          /*number of vertices in the shortest path*/

/*Store the full path in the array path*/
while( v != s )
{
count++;
path[count] = v;
u = predecessor[v];
v = u;
}
count++;
path[count]=s;

printf("\nShortest Path is : ");
for(i=count; i>=1; i--)
printf("%d  ",path[i]);
printf("\nShortest distance is : %d\n", shortdist);
}/*End of findPath()*/

void create_graph()
{
int i,max_edges,origin,destin, wt;

printf("\nEnter number of vertices : ");
scanf("%d",&n);
max_edges = n*(n-1);

for(i=1;i<=max_edges;i++)
{
printf("\nEnter edge %d( -1 -1 to quit ) : ",i);
scanf("%d %d",&origin,&destin);

if( (origin == -1) && (destin == -1) )
break;

printf("\nEnter weight for this edge : ");
scanf("%d",&wt);

if( origin >= n || destin >= n || origin<0 || destin<0)
{
printf("\nInvalid edge!\n");
i--;
}
else
}
}```

### OUTPUT : :

```/* C Program to find Shortest Distances or Path using Dijkstra's algorithm */

Enter number of vertices : 6

Enter edge 1( -1 -1 to quit ) : 0 1

Enter weight for this edge : 2

Enter edge 2( -1 -1 to quit ) : 0 2

Enter weight for this edge : 5

Enter edge 3( -1 -1 to quit ) : 0 3

Enter weight for this edge : 1

Enter edge 4( -1 -1 to quit ) : 2 4

Enter weight for this edge : 3

Enter edge 5( -1 -1 to quit ) : 2 5

Enter weight for this edge : 2

Enter edge 6( -1 -1 to quit ) : 3 4

Enter weight for this edge : 1

Enter edge 7( -1 -1 to quit ) : 4 5

Enter weight for this edge : 5

Enter edge 8( -1 -1 to quit ) : -1 -1

Enter source vertex : 0

Enter destination vertex(-1 to quit): 1

Shortest Path is : 0  1
Shortest distance is : 2

Enter destination vertex(-1 to quit): 2

Shortest Path is : 0  2
Shortest distance is : 5

Enter destination vertex(-1 to quit): 3

Shortest Path is : 0  3
Shortest distance is : 1

Enter destination vertex(-1 to quit): 4

Shortest Path is : 0  3  4
Shortest distance is : 2

Enter destination vertex(-1 to quit): 5

Shortest Path is : 0  3  4  5
Shortest distance is : 7

Enter destination vertex(-1 to quit): -1

Process returned 0```

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

#### Recommended Posts : :

5 1 vote
Article Rating

My name is Tunde Ajetomobi, a Tech Enthusiast and Growth Hacker. I enjoy creating helpful content that solves problem across different topics. Codezclub is my way of helping young aspiring programmers and students to hone their skills and find solutions on fundamental programming languages.

Subscribe
Notify of