# Dijkstra’s Algorithm in C

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, 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[ ]. ### 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 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[i];
Initially, distance of source vertex is taken as 0. i.e. distance=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(n2). ## 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

Output Comment below if you found something wrong in above dijkstra’s algorithm in C.
Category: Algorithm DSA A crazy computer and programming lover. He spend most of his time in programming, blogging and helping other programming geeks.

## 49 thoughts on “Dijkstra’s Algorithm in C”

1. Conor Wells

What does the n in the FOR loops stand for?

1. Mantas

Numbers of vertexes.

2. santhosh

thanks for giving such a best program.

3. Tyler

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.

1. Admin Post author

Thanks a lot Tyler for pointing out the mistake 🙂

1. Johnny

Please, explain, how to let user to enter the amount of vertices?
It is really important for me

2. Indra

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.

3. tall uri

for(i=1;i<n;i++)
distance[i]=cost[i];
how does it work

4. polarBear

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?

1. deadlock

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

5. Swathy R

I WORKED OUT , CODE IS CORRECT.
THANKS

1. Arbaz

Not working

6. Kostas

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.

7. Shrinivas

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.

8. iliyaz

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

9. supriya

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

10. farah

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

11. Mohammad Akram

can i get bellman ford code in this taste ?

12. mkhoda

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

13. sumit

nice ….is been hekpfull.

14. gautam

what happens if two paths have the same length

15. prathik vijaykumar

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

16. Harshit Sahu

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

1. giovani

Your 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

17. mimi

hi, 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

18. Faeshal

Dear Author
Email : [email protected]

19. Eddy

hello,
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

20. Parth Ghughriwala

The Best….

21. giovani

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

22. shubhi

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

23. vikas

Programs 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

24. santhiya

output plzz….

25. Sankalp Arora

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

26. divya

how i give infinity as input

27. Md Faisal

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

28. Ali Abdullah

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

29. Vibhor Shrotriya

very nice article
understandable

30. suppu

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.

31. Raynor

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

32. sri

can u give me the output

33. Akhil

i worked….code is correct!

34. anil

there is mistake from you

35. JOSHI RITWICK RAJIV

code works nicely

36. Ramasubramanya

Thanks a lot!
The code works well !

37. SantaFe

Explain step by step!!!!

38. Haris

Hello,
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?

39. Kota Sai Sumanth

If there is o/p it is east to understand

40. Leticia

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

41. Vaibhav Singh

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