Dijkstra Algorithm
The Dijkstra Algorithm, named after its creator, Edsger W. Dijkstra, is a widely-used graph traversal algorithm that finds the shortest path between a starting node and all other nodes in a weighted graph. Often used in routing and navigation applications, Dijkstra's algorithm works by iteratively selecting the node with the smallest known distance from the starting node, and updating the distances of its neighboring nodes based on the edge weights connecting them. This process is repeated until all nodes have been visited or the shortest path to the destination node has been determined.
In order to efficiently keep track of distances and visited nodes, the algorithm typically uses a priority queue data structure. Initially, the starting node is assigned a distance of zero, while all other nodes are assigned an infinite distance. As the algorithm progresses, it extracts nodes with the smallest distance from the priority queue, marking them as visited and updating the distances of their neighbors. This ensures that nodes are visited in the order of their proximity to the starting node, guaranteeing the discovery of the shortest path. Once the destination node has been visited or all nodes have been processed, the path can be reconstructed by tracing back from the destination node to the starting node via the shortest path tree formed during the algorithm's execution.
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<string.h>
//Structure for storing a graph
struct Graph{
int vertexNum;
int** edges;
};
//Constructs a graph with V vertices and E edges
void createGraph(struct Graph* G,int V){
G->vertexNum = V;
G->edges =(int**) malloc(V * sizeof(int*));
for(int i=0; i<V; i++){
G->edges[i] = (int*) malloc(V * sizeof(int));
for(int j=0; j<V; j++)
G->edges[i][j] = INT_MAX;
G->edges[i][i] = 0;
}
}
//Adds the given edge to the graph
void addEdge(struct Graph* G, int src, int dst, int weight){
G->edges[src][dst] = weight;
}
//Utility function to find minimum distance vertex in mdist
int minDistance(int mdist[], int vset[], int V){
int minVal = INT_MAX, minInd ;
for(int i=0; i<V;i++)
if(vset[i] == 0 && mdist[i] < minVal){
minVal = mdist[i];
minInd = i;
}
return minInd;
}
//Utility function to print distances
void print(int dist[], int V){
printf("\nVertex Distance\n");
for(int i = 0; i < V; i++){
if(dist[i] != INT_MAX)
printf("%d\t%d\n",i,dist[i]);
else
printf("%d\tINF",i);
}
}
//The main function that finds the shortest path from given source
//to all other vertices using Dijkstra's Algorithm.It doesn't work on negative
//weights
void Dijkstra(struct Graph* graph, int src){
int V = graph->vertexNum;
int mdist[V]; //Stores updated distances to vertex
int vset[V]; // vset[i] is true if the vertex i included
// in the shortest path tree
//Initialise mdist and vset. Set distance of source as zero
for(int i=0; i<V; i++)
mdist[i] = INT_MAX, vset[i] = 0;
mdist[src] = 0;
//iterate to find shortest path
for(int count = 0; count<V-1; count++){
int u = minDistance(mdist,vset,V);
vset[u] = 1;
for(int v=0; v<V; v++){
if(!vset[v] && graph->edges[u][v]!=INT_MAX && mdist[u] + graph->edges[u][v] < mdist[v])
mdist[v] = mdist[u] + graph->edges[u][v];
}
}
print(mdist, V);
return;
}
//Driver Function
int main(){
int V,E,gsrc;
int src,dst,weight;
struct Graph G;
printf("Enter number of vertices: ");
scanf("%d",&V);
printf("Enter number of edges: ");
scanf("%d",&E);
createGraph(&G,V);
for(int i=0; i<E; i++){
printf("\nEdge %d \nEnter source: ",i+1);
scanf("%d",&src);
printf("Enter destination: ");
scanf("%d",&dst);
printf("Enter weight: ");
scanf("%d",&weight);
addEdge(&G, src, dst, weight);
}
printf("\nEnter source:");
scanf("%d",&gsrc);
Dijkstra(&G,gsrc);
return 0;
}
