Here you will learn about dijkstra’s algorithm in C.

Dijkstra algorithm is also called single source shortest path algorithm. It is based on greedy technique. The algorithm maintains a list visited[ ] of vertices, whose shortest distance from the source is already known.

If visited[1], equals 1, then the shortest distance of vertex i is already known. Initially, visited[i] is marked as, for source vertex.

At each step, we mark visited[v] as 1. Vertex v is a vertex at shortest distance from the source vertex. At each step of the algorithm, shortest distance of each vertex is stored in an array distance[ ].

**Also Read: Prim’s Algorithm in C**

### Dijkstra’s Algorithm

1. Create cost matrix C[ ][ ] from adjacency matrix adj[ ][ ]. C[i][j] is the cost of going from vertex i to vertex j. If there is no edge between vertices i and j then C[i][j] is infinity.

2. Array visited[ ] is initialized to zero.

for(i=0;i<n;i++)

visited[i]=0;

3. If the vertex 0 is the source vertex then visited[0] is marked as 1.

4. Create the distance matrix, by storing the cost of vertices from vertex no. 0 to n-1 from the source vertex 0.

for(i=1;i<n;i++)

distance[i]=cost[0][i];

Initially, distance of source vertex is taken as 0. i.e. distance[0]=0;

5. for(i=1;i<n;i++)

– Choose a vertex w, such that distance[w] is minimum and visited[w] is 0. Mark visited[w] as 1.

– Recalculate the shortest distance of remaining vertices from the source.

– Only, the vertices not marked as 1 in array visited[ ] should be considered for recalculation of distance. i.e. for each vertex v

if(visited[v]==0)

distance[v]=min(distance[v],

distance[w]+cost[w][v])

### Time Complexity

The program contains two nested loops each of which has a complexity of O(n). n is number of vertices. So the complexity of algorithm is O(n

^{2}).## Program for Dijkstra’s Algorithm in C

C Program on Dijkstra Algorithm for Finding Minimum Distance of Vertices from a Given Source in a Graph

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<stdio.h> #include<conio.h> #define INFINITY 9999 #define MAX 10 void dijkstra(int G[MAX][MAX],int n,int startnode); int main() { int G[MAX][MAX],i,j,n,u; printf("Enter no. of vertices:"); scanf("%d",&n); printf("\nEnter the adjacency matrix:\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&G[i][j]); printf("\nEnter the starting node:"); scanf("%d",&u); dijkstra(G,n,u); return 0; } void dijkstra(int G[MAX][MAX],int n,int startnode) { int cost[MAX][MAX],distance[MAX],pred[MAX]; int visited[MAX],count,mindistance,nextnode,i,j; //pred[] stores the predecessor of each node //count gives the number of nodes seen so far //create the cost matrix 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]; //initialize pred[],distance[] and visited[] for(i=0;i<n;i++) { distance[i]=cost[startnode][i]; pred[i]=startnode; visited[i]=0; } distance[startnode]=0; visited[startnode]=1; count=1; while(count<n-1) { mindistance=INFINITY; //nextnode gives the node at minimum distance for(i=0;i<n;i++) if(distance[i]<mindistance&&!visited[i]) { mindistance=distance[i]; nextnode=i; } //check if a better path exists through nextnode visited[nextnode]=1; for(i=0;i<n;i++) if(!visited[i]) if(mindistance+cost[nextnode][i]<distance[i]) { distance[i]=mindistance+cost[nextnode][i]; pred[i]=nextnode; } count++; } //print the path and distance of each node for(i=0;i<n;i++) if(i!=startnode) { printf("\nDistance of node%d=%d",i,distance[i]); printf("\nPath=%d",i); j=i; do { j=pred[j]; printf("<-%d",j); }while(j!=startnode); } } |

**Output**

Comment below if you found something wrong in above dijkstra’s algorithm in C.

What does the n in the FOR loops stand for?

Numbers of vertexes.

thanks for giving such a best program.

You have a typo in step 2. The for loop should be (for i = 0; i < n; i++) visited[i] = 0; You have a "1" in the brackets so the for loop is pointless by initializing the second element over and over, n times.

Thanks a lot Tyler for pointing out the mistake 🙂

What would need to be changed in the algorithm if we have a rectangular matrix n*m? Because I have a maze of size n*m and I need to find shortest path from some spot in the maze to the exit. Any help with that?

I think you only need to set your node count to M * N.

I WORKED OUT , CODE IS CORRECT.

THANKS

im trying to short out how to make it show the distance and the path between 2 points and not all, for instance if i want to go from a to b what is the best path and the cost.

Can you please help me to convert this code to find longest path, I have tried but few problems are coming. Its very important to me, your help is more precious.

thanks dear, it is very nice program for understanding…………..

nice website. here everything is given detailed. convenient way to study for student.

this website is amazing.codes are easily understandable.i always follow this website.

can i get bellman ford code in this taste ?