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 :



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

0 0 vote
Article Rating
Notify of
Inline Feedbacks
View all comments