**Shortest Distances or Path using Dijkstra’s algorithm**

**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*

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.

- 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 : :**

**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 adj[MAX][MAX]; 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*/ pathLength[i] = pathLength[current] + adj[current][i]; } } } }/*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]; shortdist += adj[u][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 adj[origin][destin] = wt; } }

**OUTPUT : :**

**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.

**Thanks for reading the post…**

**Recommended Posts : :**

**Recommended Posts : :**

- Find whether an Undirected Graph is Cyclic or not
- Traversing Undirected Graph through DFS Recursively
- Find whether a Directed Graph is Cyclic or not
- Traversing Directed Graph through DFS and classifying all edges