Dijkstra’s Algorithm in C

Computer scientist Edsger W. Dijkstra developed Dijkstra’s Algorithm in 1956.

Introduction to Dijkstra’s Algorithm in C:

A single source shortest path algorithm is used. It means that the shortest routes between a single source vertex and all other vertices in a graph are found.

For directed, undirected, and positively weighted graphs (a graph is said to be positively weighted if all of its edges only have positive weights), it is a greedy technique. The shortest path between a source node and each other node in a network is found using the Dijkstra Algorithm, a graph algorithm.

This kind of greedy algorithm exists. It can only be used with weighted graphs that have positive weights. There is a time complexity of

Time complexity is a factor. By representing the graph as an adjacency list, where V is the number of vertices and E is the number of edges, the temporal complexity can be lowered to O((V+E) logV).

Working:

Each vertex in this algorithm will have two declared properties:

Visited Property:

1. This feature indicates whether or not the vertex has been visited.
2. In order to avoid going back to a vertex, we are leveraging this characteristic.
3. Only after the shortest path has been discovered may a vertex be recorded as visited.

Path Property:

1. The value of the most recent minimal path to the vertex is kept in this attribute. The current minimum path is the quickest route we have taken to get to this vertex so far.

2. Every time a vertex neighbour receives a visit, this property is updated.

3. The final solution for each vertex will be stored in the path property, which is crucial.

4. Since we haven’t visited any of the vertices yet, they are all initially tagged as unvisited. Except for the source vertex, the path to every vertex is set to infinity. The source vertex’s path is set to zero (0).

5. The source vertex is then selected and marked as visited. The source vertex’s neighbours are then all accessed, and each vertex is relaxed after that. The act of relaxing involves making an effort to make using another vertex to reach one vertex more affordable.

6. Each vertex’s path is modified during relaxation to the value that is least between the node’s current path and the sum of its preceding node’s path plus this node’s path.

Considering p[v] is

1. Relaxation can be represented as: p[v] = minimum(p[v], p[n] +w)

2. The neighboring vertices routes are updated and an unvisited vertex with the lowest path value is marked as visited in each succeeding step.

3. The aforementioned procedure is repeated until all of the graph’s vertices are indicated as visited.

4. The path to all of a vertex’s nearby vertices is adjusted whenever a vertex is added to the visited set.

5. The route of any unreachable (disconnected component) vertex stays infinite. The path to all subsequent vertices remains infinite if the source is a disconnected component.

Algorithm for Dijkstra’s Algorithm:

1. Set the current distance for the source node to 0 and the rest to infinity.

2. Assign C as the current node, which is the non-visited node with the shortest current distance.

3. The current distance between node C and each of its neighbours, N, is added together with the edge’s edge weight. If it is less than N’s existing distance, N’s new current distance will be determined by its lesser size.

4. Identify the current node C as visited.

5. If any nodes are still unvisited, proceed to step 2.

Example:

1. Let’s use the graph shown below as our input, with vertex a serving as the source.

2. All of the vertices are initially tagged as unvisited.

3. The path from a to all other vertices is set to infinity and is equal to 0.

4. The source vertex a has been noted as visited at this time. The neighborhood’s neighbours are then accessed (although not physically visited).

5. The relaxation updates the path to b to 4 because the path from a to b is 4 and the path to an is 0; hence, the value of min ((0+4)) is 4.

6. The relaxation updates the path to c to 5 because the path from a to c is 5 and the path to an is 0; hence, the value of min ((0+5)) is 5.

We continue since a’s neighbours on each side are at ease.

The last paths we receive are:

a = 0(source)
b =4(a → b)
c = 5(a → c)
d = 13(a → b → 8)
e = 8(a → c → e)
f = 14! (a → c → e → f)

Implementation of Dijkstra Algorithm:

#include<stdio.h>
#define INFINITY 9999
#define MAX 10
void dijikstra(int G[MAX][MAX], int n, int start);
void main(){
int g[MAX][MAX], i, j, num, u;
printf(“\nEnter the no. of vertices:: “);
scanf(“%d”, &num);
printf(“\nEnter the adjacency matrix::\n”);
for(i=0;i < num;i++)
for(j=0;j < num;j++)
scanf(“%d”, &g[i][j]);
printf(“\nEnter the starting node:: “);
scanf(“%d”, &u);
dijikstra(g,num,u);
}
void dijikstra(int g[MAX][MAX], int num, int start)
{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visit[MAX], count, mindistance, next, i,j;
for(i=0;i < num;i++)
for(j=0;j < num;j++)
if(g[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=g[i][j];
for(i=0;i< num;i++)
{
distance[i]=cost[start][i];
pred[i]=start;
visit[i]=0;
}
distance[start]=0;
visit[start]=1;
count=1;
while(count < num-1){
mindistance=INFINITY;
for(i=0;i < num;i++)
if(distance[i] < mindistance&&!visit[i])
{
mindistance=distance[i];
next=i;
}
visit[next]=1;
for(i=0;i < num;i++)
if(!visit[i])
if(mindistance+cost[next][i] < distance[i])
{
distance[i]=mindistance+cost[next][i];
pred[i]=next;
}
count++;
}
for(i=0;i < num;i++)
if(i!=start)
{
printf(“\nDistance of %d = %d”, i, distance[i]);
printf(“\nPath = %d”, i);
j=i;
do
{
j=pred[j];
printf(“ <-%d”, j);
}
while(j!=start);
}
}

Output:

Time Complexity in Dijkstra Algorithm:

Dijkstra’s algorithm complexity study using the graph’s adjacency matrix representation.

The Dijkstra algorithm has a time complexity of (2) O (V 2), where V is the number of vertex in the graph.

This is how it can be explained:

Finding the unvisited vertex with the shortest path must come first. We need () O(V) time for that since we must examine each vertex.

The next step is to update each neighbour’s path to the smaller value between the current path and the newly discovered path for each vertex picked as above.

One neighbour’s relaxation takes about O (1) (continuous time) worth of time.

All of the vertices’ neighbours must be relaxed for each vertex.

As a result of the aforementioned circumstances, we get:

Time to visit every vertex is O(V).
Processing time for a single vertex is O(V).
The amount of time needed to visit and process each vertex is O(V)*O(V)=O(V2)
Adjacency list representation allows the time complexity of Dijkstra’s method to be decreased to O((V+E) logV)
Time to visit every vertex is O(V+E).
O(logV) is the time necessary to process one vertex.
The amount of time needed to visit and process each vertex
=O(V+E) ∗O(logV)=O((V+E) logV)

Since both the adjacency list and the min-heap require O(V) space, the space complexity in this instance will likewise decrease to O(V). Consequently, the overall space complexity is O(V)+O(V)=O(2V) =O(V)

Dijkstra Applications:

The Dijkstra algorithm has a variety of uses:

1. Consider using a digital mapping service like Google Maps to move from one city to another. Assume that your current location is a source vertex and that your destination is a different vertex.
2. Between your final destination and the starting place, there are still numerous cities. Assume that those cities are middle vertices. You can suppose that the weight between any pair of vertices is equal to the distance and traffic between any two cities. The shortest route will be discovered by Google Maps using the Dijkstra algorithm on the city graph.
3. Designate Servers: Dijkstra’s Algorithm can be used in a network to determine the shortest path to a server for file transmission among the participants.