Single Source Shortest Path using Dijkstra's Algorithm

Dijkstra's algorithm solves the single source shortest path problem when all edges have non negative weights. algorithm starts at the source vertex S, it grows a tree that ultimately spans all vertices reachable from S. Vertices are added to tree in order of distance i.e., first S, the vertices closest to S, then the next closest and so on.

Dijkstra(G, W, S)
S<-{}
Initialize priority queue Q i.e.,Q<-V[G]
while priority queue Q is not empty do
    u<-Extract_Min(Q)
S<-S ⋃ {u}
for each vertex v ∈ Adj[u] do
    Relax(u, v, w)    				
			

Relax(u, v, w)
if d[u] + w(u, v) < d[v] then
    d[v]<-d[u] + w(u, v)
    π[v]<-u				
			

Let's take an example which is shown below in the Fig 1.

Step 1:All nodes have set infinite distance except the source node S which is set as 0.

Step 2:Relax all nodes adjacent to source S.Adj[s]={u, x}.

Apply relax(s, u, w) and relax(s, x, w)

Step 3:Choose the closest node x.Relax all nodes adjacent to x.Adj[x]={u, y, v}

Apply relax(x, u, w) ,relax(x, u, w) and relax(x, v, w)

Step 4:Now, node y is the closest node.Adj[y]={v}

Apply relax(y, v, w)

Step 5:Now, the closest node is u.Adj[u]={v, x}

Relax (u, x, w) and relax(u, v, w)

Step 6:Finally, we get the shortest distance of each vertex from the source s.

Source code

#include<stdio.h> #include<stdlib.h> #include<limits.h> void dijstra(int n, int v, int **cost, int *dist) { int i, u, count, w, *flag, min; flag = (int *)malloc(n * sizeof(int)); for (i = 0; i < n; i++) flag[i] = 0, dist[i] = cost[v][i]; count = 1; while (count < n) { min = 999; for (w = 0; w < n; w++) if (dist[w] < min && !flag[w]) min = dist[w], u = w; flag[u] = 1; count++; for (w = 0; w < n; w++) if ((dist[u] + cost[u][w] < dist[w]) && !flag[w]) dist[w] = dist[u] + cost[u][w]; } } int main() { int n, v, i, j, **cost, *dist; printf("\n Enter the number of nodes:"); scanf("%d", &n); cost = (int **)malloc(n * sizeof(int *)); for(i = 0; i < n; i++) cost[i] = (int *)malloc(n * sizeof(int)); dist = (int *)malloc(n * sizeof(int)); printf("\n Enter the cost matrix:\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", &cost[i][j]); if (cost[i][j] == 0) cost[i][j] = INT_MAX; } } printf("\n Enter the source node:"); scanf("%d", &v); dijstra(n, v, cost, dist); printf("\n Shortest path:\n"); for (i = 0; i < n; i++) if (i != v) printf("%d->%d,cost=%d\n", v, i, dist[i]); return 0; }

Happy Exploring!