Page No.
PROBLEM STATEMENT:-
Write a program in c to find the shortest path for a graph using dijkstra’s algorithm.
THEORY:-
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we
generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains
vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree.
At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has
a minimum distance from the source.
Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source
vertex to all other vertices in the given graph.
Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree,
i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE.
Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSet and has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through
all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight
of edge u-v, is less than the distance value of v, then update the distance value of v.
ALGORITHM: -
Variable Listing: -
Variable Type Purpose
n integer Indicate the no of vertices to be
input
v integer Indicate the source vertex of
the graph
i,j integer Incremental operators used in
loops
cost[][] integer It is used to input the cost
matrix
dist[] integer It indicates the total cost
Steps for calling the function prototype-int dijk(int n,int v,int cost[10][10],int dist[]): -
STEP 1: - Input i,u,count,w,flag[10],min
STEP 2: - Repeat through step 3 step 15 for i=1 to n
STEP 3: - Set flag[i]=0
Date: -
Page No.
STEP 4: - Set dist[i]=cost[v][i]
STEP 5: - Set count=2
STEP 6: - Repeat through step 7 to step 15 while(count<=n)do
STEP 7: - Set min=99
STEP 8: - Repeat through step 9 to step 15 for w=1 to n
STEP 9: - if(dist[w]<min & !flag[w])
STEP 10: - Set min=dist[w],u=w
STEP 11: - Set flag[u]=1
STEP 12: - Increment count by 1
STEP 13: - Repeat through step 14 to step 15 for w=1 to n
STEP 14: - if((dist[u]+cost[u][w]<dist[w] & !flag[w]) then
STEP 15: - Set dist[w]=dist[u]+cost[u][w]
[End of if]
[End of for loop]
[End of for loop]
[End of while loop]
[End of for loop]
STEP 16: - Stop
Start of main() function: -
STEP 1: - Input n,v,i,j,cost[10][10],dist[10]
STEP 2: - Input the no of vertices
STEP 3: - Read n
STEP 4: - Input “cost matrix”
STEP 5: - Repeat through step 6 to step for i=1 to n
STEP 6: - Repeat through step 7 to step for j=1 to n
STEP 7: - Read cost[i][j]
STEP 8: - If(cost[i][j]=0) then
STEP 9: - Set cost[i][j]=infinity
[End of for loop]
Date: -
Page No.
STEP 10: - Input “enter the source vertex”
STEP 11: - Read v
STEP 12: - call the function dijk(n,v,cost,dist)
STEP 13: - Display “the shortest path”
STEP 14: - Repeat through step 15 to step for i=1 to n
STEP 15: - If(i!=v) then
STEP 16: - Display “%d->%d,cost=%d\n”,v,i,dist[i]
[End of for loop]
[End of for loop defined at step 5]
STEP 17: -Stop
SOURCE CODE: -
#include<stdio.h>
#define infinity 9999
int dij(int n,int v,int cost[10][10],int dist[])
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0;
dist[i]=cost[v][i];
count=2;
while(count<=n)
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
Date: -
Page No.
count++;
for(w=1;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[10][10],dist[10];
printf("\n enter the no of vertices");
scanf("%d",&n);
printf("\n enter the cost matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=infinity;
printf("\n enter the source matrix");
Date: -
Page No.
scanf("%d",&v);
dij(n,v,cost,dist);
printf("\n shortest path\n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d\n",v,i,dist[i]);
return 0;
INPUT & OUTPUT: -
Set 1: - enter the no of vertices 4
enter the cost matrix
2345
enter the source matrix
5671
shortest path
5->1,cost=0
5->2,cost=3
5->3,cost=0
5->4,cost=0
--------------------------------
Process exited after 69.57 seconds with return value 0
Press any key to continue . . .
Set 2: - enter the no of vertices 5
enter the cost matrix
Date: -
Page No.
27934
enter the source matrix
61582
shortest path
6->1,cost=0
6->2,cost=-589060154
6->3,cost=9
6->4,cost=3
6->5,cost=0
--------------------------------
Process exited after 64.94 seconds with return value 0
Press any key to continue . . .
DISCUSSION: -
1) The code calculates shortest distance, but doesn’t calculate the path information. We can create a
parent array, update the parent array when distance is updated (like prim’s implementation) and use it
show the shortest path from source to different vertices.
2) The code is for undirected graph, same dijkstra function can be used for directed graphs also.
3) The code finds shortest distances from source to all vertices. If we are interested only in shortest
distance from the source to a single target, we can break the for the loop when the picked minimum
distance vertex is equal to target (Step 3.a of the algorithm).
4) Time Complexity of the implementation is O(V^2). If the input graph is represented using adjacency
list, it can be reduced to O(E log V) with the help of binary heap.
Date: -
