C Program To Implement Dijkstra’s Algorithm To Find Shortest Path
Let us learn how to implement Dijkstra’s Algorithm in C programming using Adjacency Matrix.
The Dijkstra Algorithm is used to find the shortest path in a weighted graph.
What is Dijkstra’s Algorithm?
Dijkstra’s 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 this algorithm.
In any graph G, the shortest path from a source vertex to a destination vertex can be calculated using Dijkstra 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.
This algorithm is similar to Prim’s Algorithm to find the minimum spanning trees. The Dijkstra’s algorithm works only for graphs having non – negative weights.
Steps for Dijkstra’s Sequence of Action
- Set the pathLength of all the vertices to Infinity, the predecessor of all the vertices to NIL and the status of all the vertices to temporary.
- Set pathLength of source vertex to Zero.
- 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.
- 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.
- 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
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | #include<stdio.h> #define MAX 100 #define NIL -1 #define infinity 9999 #define TEMPORARY 0 #define PERMANENT 1 void Path_Finder(int source, int vertex); void Dijkstra_function(int source); int minimum_temp(); void make_graph(); int vertices; int adjacent_matrix[MAX][MAX]; int predecessor[MAX]; int vertex_status[MAX]; int pathLength[MAX]; int main() { int source, vertex; make_graph(); printf("Enter Source Vertex:\t"); scanf("%d", &source); Dijkstra_function(source); while(1) { printf("Enter destination vertex(-1 to Quit):\t"); scanf("%d", &vertex); if(vertex == -1) { break; } if(vertex < 0 || vertex >= vertices) { printf("The Entered Vertex does not exist\n"); } else if(vertex == source) { printf("Source Vertex and Destination Vertex are same\n"); } else if(pathLength[vertex] == infinity) { printf("There is no path from Source vertex to Destination vertex\n"); } else { Path_Finder(source, vertex); } } return 0; } void Dijkstra_function(int source) { int count, current; for(count = 0; count < vertices; count++) { predecessor[count] = NIL; pathLength[count] = infinity; vertex_status[count] = TEMPORARY; } pathLength[source] = 0; while(1) { current = minimum_temp(); if(current == NIL) { return; } vertex_status[current] = PERMANENT; for(count = 0; count < vertices; count++) { if(adjacent_matrix[current][count] != 0 && vertex_status[count] == TEMPORARY) { if( pathLength[current] + adjacent_matrix[current][count] < pathLength[count]) { predecessor[count] = current; pathLength[count] = pathLength[current] + adjacent_matrix[current][count]; } } } } } int minimum_temp() { int count; int min = infinity; int x = NIL; for(count = 0; count < vertices; count++) { if(vertex_status[count] == TEMPORARY && pathLength[count] < min) { min = pathLength[count]; x = count; } } return x; } void Path_Finder(int source, int vertex) { int count, u; int path[MAX]; int shortest_distance = 0; int temp = 0; while(vertex != source) { temp++; path[temp] = vertex; u = predecessor[vertex]; shortest_distance = shortest_distance + adjacent_matrix[u][vertex]; vertex = u; } count++; path[temp] = source; printf("Shortest Path\n"); for(count = temp; count >= 1; count--) { printf("%d ", path[count]); } printf("\nShortest distance:\t%d\n", shortest_distance); } void make_graph() { int count, maximum_edges, origin_vertex, destination_vertex, weight; printf("Enter total number of vertices:\t"); scanf("%d", &vertices); maximum_edges = vertices * (vertices - 1); for(count = 0; count < maximum_edges; count++) { printf("Enter Edge [%d] Co-ordinates [-1 -1] to Quit\n", count + 1); printf("Enter Origin Vertex Point:\t"); scanf("%d", &origin_vertex); printf("Enter Destination Vertex Point:\t"); scanf("%d", &destination_vertex); if((origin_vertex == -1) && (destination_vertex == -1)) { break; } printf("Enter the weight for this edge:\t"); scanf("%d", &weight); if(origin_vertex >= vertices || destination_vertex >= vertices || origin_vertex < 0 || destination_vertex < 0) { printf("Edge Co - ordinates are Invalid\n"); count--; } else { adjacent_matrix[origin_vertex][destination_vertex] = weight; } } } |
Must Read: C Program For Travelling Salesman Problem
Output
In case you get any compilation errors or any doubts in this code for Dijkstra’s Algorithm in C programming for finding the shortest path, let us know about it in the comment section below.
What other algorithms are used to find out Shortest Path for a weighted graph apart from the Dijkstra’s Algorithm?
I believe this is the perfect code for Dijkstra’s algorithm in c programming. It is well written and formatted properly.
The Dijkstra algorithm explanation is really what I was looking for. Thank you so much.
One of the best of dijkstra’s algorithm using adjacency matrix that i have seen. Dijkstra algorithm is however comparatively difficult to understand.
Dijkstra’ algorithm can also be implemented using a priority queue in C programming.
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
Doesn’t matter what path you think of, the program always skips the second vertex on that path.
For example: You think of a path that should be returned as the shortest (e.g.: 0 3 5 ), the program however returns ( 0 5 ).
Any ideas why this happens?
This program doesn’t work for all examples.
Couldn’t attach the screenshot of the graph unfortunately.
It works perfectly but how do i get the path taken from beginning to end to show properly, I believe it only shows the first one and some in between an the last one.