C Mini Projects for Students Dijkstra’s Algorithm
C Mini Projects for Students Dijkstra’s Algorithm:
Are you a Bsc., or Diploma student?… Searching help to do your Mini Projects in C?… Try the following C Mini Project based on Dijkstra’s Algorithm. A simple shortest path algorithm application.
Scope of the project:
To find the shortest path (with less distance) between two nodes of a weighted and directed graph.
- Dijkstra’s Algorithm is one of the shortest-path algorithms.
- This Dijkstra’s Algorithm is evolved to overcome the problems of single-source shortest-path problem.
- Dijkstra’s Algorithm was found by Edsger Wybe Dijkstra in the year 1956.
Uses of Dijkstra’s Algorithm:
- To find the shortest path between different nodes of a graph.
- It is used to solve routing problems sometimes.
- It is also used by other graph algorithms as subroutines.
What is Dijkstra’s Algorithm?
Dijkstra’s Algorithm is the best algorithm that finds solution for the single source shortest path algorithm only when a weighted, directed graph contains non-weighted edge weights.
Now lets see how we are going to implement the C coding for Dijkstra’s Algorithm in finding the shortest path between the nodes of a graph.
C Mini Project Dijkstra’s Algorithm:
- Consider a weighted and directed graph .
- Lets consider input of our C Program be the source, target and weight of the path between the two nodes of the graph.
- Fix any node of the graph as ‘initial node’, the starting point.
- Assume ‘Y’ as the distance between the initial node and another node, ‘y’ of the graph.
- Assign initial distance values to each node of the graph. This value can be improved step by step later through Dijkstra’s algorithm.
- Assign distance value of the initial node as zero and infinity for other nodes.
- All the nodes are set as unvisited and the initial node is set as current node.
- Create a set of unvisited nodes called as “unvisited set”.
- For the current node, calculate the tentative value for the nearby unvisited nodes.
For each node, compare the assigned current value and calculated tentative value. Then fix the smaller value.
Example: If the current node ‘X’ has distance as 3 with the node ‘Y’. Now if the edge has value ‘1’ between X and Y. Now calculate the tentative distance as 3+1=4. If the initially assigned value for ‘Y’ is less than 4, then keep that value as it is. Otherwise, set the tentative value as 4.
- After calculating tentative value to the neighboring nodes of the current value, remove it from unvisited set. Assign them as visited nodes.
- The algorithm stopped under two cases:
Case 1: While finding the route between two nodes, among which if one is the destination node and that node is marked as visited, the algorithm stops.
Case 2: If the smallest tentative value of the nodes is infinity in a complete traversal, algorithm stops. In this case, the result is there is no connection between the unvisited nodes and the initial current node.
- Set the unvisited node with smallest tentative value as current node. Repeat the algorithm from step: 4 . Continue again.
C Program For Dijkstra’s algorithm:
<span style="color: #000000;">/* Dijkstra's Algorithm in C */
// include header files
// set IN an N values globally in the header itself
#define IN 99 //distance of edge between two nodes x and y set initially
#define N 6 // cost set initially
// function prototype :dijkistra's algorithm to calculate distance between source and destination
int dij(int cost[N], int source, int destinate);
int source, destinate,x,y;
printf("\t Program to find Shortest Path using DIJKSTRA'S ALGORITHM in C \n\n");
cost[i][j] = IN;
printf("Enter the actual weight of the path between nodes %d and %d: ",x,y);
cost [x][y] = cost[y][x] = w;
printf("\nEnter the source node:");
printf("\nEnter the destination node");
co = dijsktra(cost,source,destinate);
printf("\nThe Shortest Path betweeen the nodes: %d",co);
// **** End of Main ***//
// method to Find shortest path
int dij(int cost[N],int source,int destinate)
dist[i] = IN;
prev[i] = -1;
start = source;
dist[start] = 0;
min = IN;
m = 0;
d = dist[start] +cost[start][i];
dist[i] = d;
prev[i] = start;
if(min>dist[i] && selected[i]==0)
min = dist[i];
m = i;
start = m;
selected[start] = 1;
j = 0;
while(start != -1)
path[j++] = start+65;
start = prev[start];
//*** end of dijkstra's routine***//
/********** Program ends **************/
Hope all you have well understood the Dijkstra’s algorithm along its implementation in the above C Mini Project Dijkstra’s Algorithm.
Apply the above code for your own graph and test the code. All the best…
You May Also Like to Read:
C Program For Prims Algorithm Using Greedy Method
C Mini Project for Diploma students: Binary Tree Implementation
Frequently Asked C Interview Questions for Freshers: Set-1
C Functions Interview Questions for Freshers
Thanks for reading…..
Please leave your comments below….