Dijkstra's Algorithm
AIM:
To implement Dijkstra’s algorithm to find shortest path in the graph
Description:
In this program, an un-directed graph is created, and then Dijkstra's shortest path algorithm is performed.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int e;
int adjMat[20][20];
};
struct Graph* createGraph(int v,int e)
{
int i,j,src,dest,weight;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=v;
g->e=e;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
g->adjMat[i][j]=0;
}
}
return g;
}
void insertEdges(struct Graph* g)
{
int i,src,dest,weight;
printf("\n Enter Source and Destination Vertices for each edge: ");
i=0;
while(i<g->e)
{
printf("\n Edge %d : ",i+1);
printf("\n Source Vertex : ");
scanf("%d",&src);
printf(" Destination Vertex : ");
scanf("%d",&dest);
if(src>g->v||dest>g->v)
{
printf("\n Vertex does not exists! Enter Again! \n");
}
else if(g->adjMat[src][dest]>0)
{
printf("\n Edge already exists! Enter Again! \n");
}
else
{
printf(" Enter Weight : ");
scanf("%d",&weight);
g->adjMat[src][dest]=weight;
g->adjMat[dest][src]=weight;
i++;
}
}
}
void displayGraph(struct Graph* g)
{
int i,j;
printf("\n Adjacency Matrix Representation : \n");
for(i=0;i<g->v;i++)
{
printf("\n");
for(j=0;j<g->v;j++)
{
printf(" %d\t",g->adjMat[i][j]);
}
}
printf("\n");
}
int minDistance(struct Graph* g,int dist[100],int SPT[100])
{
int i,minIndex,Min=INT_MAX;
for(i=0;i<g->v;i++)
{
if(SPT[i]==0&&dist[i]<=Min)
{
Min=dist[i];
minIndex=i;
}
}
return minIndex;
}
void dijkstraAlgo(struct Graph* g)
{
int i,j,k,TC,dist[g->v],key[g->v],parent[g->v],SPT[g->v];
for(i=0;i<g->v;i++)
{
dist[i]=INT_MAX;
SPT[i]=0;
}
dist[0]=0;
parent[0]=-1;
for(i=0;i<g->v-1;i++)
{
j=minDistance(g,dist,SPT);
SPT[j]=1;
for(k=0;k<g->v;k++)
{
if(!SPT[k]&&g->adjMat[j][k]&&dist[j]!=INT_MAX&&dist[j]+g->adjMat[j][k]<dist[k])
{
parent[k]=j;
key[k]=g->adjMat[j][k];
dist[k]=dist[j]+g->adjMat[j][k];
}
}
}
printf("\n Dijkstra's Shortest Path Algorithm :- \n");
printf("\n Vertex \t Distance from Source \n");
for(i=0;i<g->v;i++)
{
printf("\n %d \t\t %d ",i,dist[i]);
}
printf("\n\n Final Graph : ");
struct Graph* FG=createGraph(g->v,g->v-1);
TC=0;
for(i=1;i<g->v;i++)
{
FG->adjMat[parent[i]][i]=g->adjMat[i][parent[i]];
FG->adjMat[i][parent[i]]=g->adjMat[i][parent[i]];
TC=TC+g->adjMat[i][parent[i]];
}
displayGraph(FG);
printf("\n Total Cost of MST = %d ",TC);
}
int main()
{
int v,e;
printf("\n Enter No. of Vertices: ");
scanf("%d",&v);
printf("\n Enter No. of Edges: ");
scanf("%d",&e);
struct Graph* g=createGraph(v,e);
insertEdges(g);
displayGraph(g);
dijkstraAlgo(g);
return 0;
}
OUTPUT
Enter No. of Vertices: 9
Enter No. of Edges: 14
Enter Source and Destination Vertices for each edge:
Edge 1 :
Source Vertex : 0
Destination Vertex : 1
Enter Weight : 4
Edge 2 :
Source Vertex : 0
Destination Vertex : 7
Enter Weight : 8
Edge 3 :
Source Vertex : 1
Destination Vertex : 2
Enter Weight : 8
Edge 4 :
Source Vertex : 1
Destination Vertex : 7
Enter Weight : 11
Edge 5 :
Source Vertex : 2
Destination Vertex : 3
Enter Weight : 7
Edge 6 :
Source Vertex : 2
Destination Vertex : 5
Enter Weight : 4
Edge 7 :
Source Vertex : 2
Destination Vertex : 8
Enter Weight : 2
Edge 8 :
Source Vertex : 3
Destination Vertex : 4
Enter Weight : 9
Edge 9 :
Source Vertex : 3
Destination Vertex : 5
Enter Weight : 14
Edge 10 :
Source Vertex : 4
Destination Vertex : 5
Enter Weight : 10
Edge 11 :
Source Vertex : 5
Destination Vertex : 6
Enter Weight : 2
Edge 12 :
Source Vertex : 6
Destination Vertex : 7
Enter Weight : 1
Edge 13 :
Source Vertex : 6
Destination Vertex : 8
Enter Weight : 6
Edge 14 :
Source Vertex : 7
Destination Vertex : 8
Enter Weight : 7
Adjacency Matrix Representation :
0 4 0 0 0 0 0 8 0
4 0 8 0 0 0 0 11 0
0 8 0 7 0 4 0 0 2
0 0 7 0 9 14 0 0 0
0 0 0 9 0 10 0 0 0
0 0 4 14 10 0 2 0 0
0 0 0 0 0 2 0 1 6
8 11 0 0 0 0 1 0 7
0 0 2 0 0 0 6 7 0
Dijkstra's Shortest Path Algorithm :-
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
Final Graph :
Adjacency Matrix Representation :
0 4 0 0 0 0 0 8 0
4 0 8 0 0 0 0 0 0
0 8 0 7 0 0 0 0 2
0 0 7 0 0 0 0 0 0
0 0 0 0 0 10 0 0 0
0 0 0 0 10 0 2 0 0
0 0 0 0 0 2 0 1 0
8 0 0 0 0 0 1 0 0
0 0 2 0 0 0 0 0 0
Total Cost of MST = 42
--------------------------------
Process exited after 3.575 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment