Dijkstra’s Algorithm C Program

C Program To Implement Dijkstra’s Algorithm To Find Shortest Path

Learn How To Implement Dijkstra’s Algorithm in C Programming using Adjacency Matrix. The Dijkstra’s Algorithm is used to find the shortest path in a weighted graph.


What is Dijkstra’s Algorithm?

Dijkstras Algorithm is useful for finding the shortest path in a weighted graph. In any graph G, the shortest path from a source vertex to a destination vertex can be calculated using Dijkstra’s Algorithm.

Must Read: C Program To Implement Kruskal’s Algorithm

Every vertex is labelled with pathLength and predecessor. The pathLength denotes the shortest path whereas the predecessor denotes the predecessor of a given vertex in a path. The values of the pathLength and predecessor can be updated more than once in this algorithm. Initially, all the vertices are made Temporary. If a vertex is made Permanent, it means that the shortest distance has been found out. Once a vertex is made permanent, then the values of the pathLength and predecessor for it become fixed and cannot be changed thereafter.

Dijkstras Algorithm is similar to Prim’s Algorithm To Find Minimum Spanning Trees. Dijkstras Algorithm works only for graphs having non – negative weights.

Dijkstras Algorithm in C Programming using Adjacency Matrix

Steps for Dijkstra’s Algorithm

 


  1. Set the pathLength of all the vertices to Infinity, predecessor of all the vertices to NIL and the status of all the vertices to temporary.
  2. Set pathLength of source vertex to Zero.
  3. Find the vertex that has the minimum value of pathLength by checking all the vertices in the graph and set its status as Permanent and consider it as the current vertex.
  4. Check all the temporary vertices adjacent to the current vertex. Now, the value of the pathLength is recalculated for all these temporary successors of current vertex, and relabelling is done if needed.
  5. Repeat the steps 3 and 4 until there is no temporary vertex remaining in the graph. In case if there are any vertices left, then they must have pathLength as Infinity.

Must Read: C Program To Implement Sliding Window Algorithm

C Program For Dijkstra’s Algorithm using Adjacency Matrix

Must Read: C Program For Travelling Salesman Problem

Output

C Program For Dijkstra's Algorithm To Find Shortest Path

In case you get any Compilation Errors or any doubts in this C Program For Dijkstra’s Algorithm for finding Shortest Path, let us know about it in the Comment Section below. Find more about this algorithm on Wikipedia.

Tushar Soni

I am Tushar Soni, Co - Founder of CodingAlpha. I am a computer science student from India and passionate about Web Development and Programming. Connect with me on Facebook | LinkedIn | Google Plus

7 thoughts on “Dijkstra’s Algorithm C Program

  • October 1, 2016 at 10:47 am
    Permalink

    What other algorithms are used to find out Shortest Path for a weighted graph apart from the Dijkstra’s Algorithm?

    Reply
  • October 2, 2016 at 7:29 pm
    Permalink

    I believe this is the perfect code for Dijkstra’s algorithm in c programming. It is well written and formatted properly.

    Reply
  • October 2, 2016 at 7:30 pm
    Permalink

    The Dijkstra algorithm explanation is really what I was looking for. Thank you so much.

    Reply
  • October 5, 2016 at 3:37 pm
    Permalink

    One of the best of dijkstra’s algorithm using adjacency matrix that i have seen. Dijkstra algorithm is however comparatively difficult to understand.

    Reply
  • October 17, 2016 at 11:21 am
    Permalink

    Dijkstra’ algorithm can also be implemented using a priority queue in C programming.

    Reply
  • May 8, 2017 at 4:32 am
    Permalink

    Hello! Can I ask what is the complete condition in line 147? I cannot see what is after the ‘origin_vertex < 0 ||' with my browser. I'm just a newbie in programming, that's why I do not know how to fill the blanks

    Reply

Join The Discussion