Here you will learn about Dijkstra’s algorithm and how you can implement it in C programming.

Dijkstra algorithm is also called the single source shortest path algorithm. It is based on the 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 the shortest distance from the source vertex. At each step of the algorithm, the 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, the distance of the 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 the 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 the number of vertices. So the complexity of the algorithm is O(n^{2}).

## Dijkstra’s Algorithm Program in C

Here is the C Program on Dijkstra Algorithm for finding the 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:**

This program calculates the shortest distance from the starting node to all the other nodes in the graph. It also prints the distance and the path from the starting node to each node.

The algorithm works by maintaining a list of visited nodes. And for each unvisited node, it calculates the distance to that node from the starting node and updates the distance and the path if a shorter path is found.

The algorithm continues until all nodes have been visited, and the shortest distance and the path to each node have been calculated.

Now I hope you know how to implement this algorithm in C. Comment below if you have any queries or found something wrong in Dijkstra’s algorithm in C.

Conor WellsWhat does the n in the FOR loops stand for?

MantasNumbers of vertexes.

santhoshthanks for giving such a best program.

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

AdminThanks a lot Tyler for pointing out the mistake 🙂

JohnnyPlease, explain, how to let user to enter the amount of vertices?

It is really important for me

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

tall urifor(i=1;i<n;i++)

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

how does it work

polarBearWhat 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?

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

Swathy RI WORKED OUT , CODE IS CORRECT.

THANKS

ArbazNot working

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

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

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

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

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

Mohammad Akramcan i get bellman ford code in this taste ?

mkhodaHey, could you please modify your code to find the k-shortest path. It would be much appreciated. Thanks

sumitnice ….is been hekpfull.

gautamwhat happens if two paths have the same length

prathik vijaykumarhey the code is running properly for 9 vertices, but is giving problems when the number of vertices are 16. your help will be valuable

VishnuMAX is defined to 10. So it works upto 10 vertices, change it to 16

Vishnu cmrChanging MAX works

Harshit SahuI have an adjacency matrix of 25 by 25. The code isn’t working for the following. What should I do?

giovaniYour matrix is ti big, change the variable MAX to be 25 or 26, to be safe. You can find it in the first line of codes wheere is the keyword DEFINE

mimihi, im having problem for my assignment. i have assign to do a shortest path in GPS system code in c.

where i need to create a map or path and ask the user to insert starting point and destination and we also have to calculate and display 3 shortest path based on ranking and display the history record

FaeshalDear Author

Please help me to created shorthest path and longest path distance in one program , how to add longest path distance in that code in dev c++ ? . i have try but always error for add longest path distance Please help me , i beg to you for my assignment , please sir help me . you can send in my email the code , anyone please help me , its important.

Email : [email protected]

Eddyhello,

nice code , but i think something is missing.

your program will show the paths to the other nodes but , if I want the shortest path from a specific source to a specific destination?

one more variable is required

Parth GhughriwalaThe Best….

giovaniThanks dude! This helped me a lot in understanding the algorithm, cheers! 🙂

shubhihow do you find the execution time of the above program?

vikasPrograms are witten in difficult ways.

What I found that a program is considered best in written complex way.

But any software program is considered in written is simple and understandable manner.

There might be hundreds of ways to write A+B=C but in India the one with max number of code lines would fetch max marks irrespective if its worth or fuddu

santhiyaoutput plzz….

Sankalp AroraWhy haven’t we first created a graph and then used its adjacency matrix, for further work. Isn’t it wrong just to have a 2-D array and applying the stuff to it?

divyahow i give infinity as input

Md FaisalPlz anybody help me i need to find the longest path…anyone give me the full code plz

Ali AbdullahThis does not work if I add other ways to get n, u and G

Vibhor Shrotriyavery nice article

understandable

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

RaynorWhat is the “!visited”? Is it like “visited != 0”??

srican u give me the output

Akhili worked….code is correct!

anilthere is mistake from you

JOSHI RITWICK RAJIVcode works nicely

RamasubramanyaThanks a lot!

The code works well !

SantaFeExplain step by step!!!!

HarisHello,

Can you please explain me how it works?

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);

}

why pred[j] is the previus node?

dandont know

Kota Sai SumanthIf there is o/p it is east to understand

Shreemoti jotti royYes, it work loop

LeticiaI get segmentation fault while running this program. Could anybody help?

Vaibhav SinghCan anyone explain how the paths are printing means how the do while loop is working

MilenaHi , thank you for this beautiful code, now i understand Djikstra algorithm 🙂

I’ll use it to model points and streets on a map to find the shortest driving way, like GPS 😀