-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS Directed Shortest Path.c
147 lines (127 loc) · 2.38 KB
/
BFS Directed Shortest Path.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
Problem Statement - Implementation of BFS on an directed, non-weighted graph to get shortest path
*/
#include <stdio.h>
#define MAX 10
int adj[MAX][MAX],queue[MAX],visited[MAX],path[MAX],v=0,front=-1,rear=-1,dist=0;
void insert(int x)
{
if(rear==-1)
front++;
queue[++rear]=x;
}
int del()
{
return(queue[front++]);
}
void printer(int s,int d)
{
if(s==d)
{
printf("%d",s+1);
return;
}
else
{
printer(s,path[d]);
printf("---> %d",d+1);
}
}
int bfs(int start,int d)
{
int node,i,j;
insert(start);
printf("\n\n");
do
{
node=del();
// if(visited[node]==0)
// {
visited[node]=1;
for(i=0;i<v;i++)
{
if(adj[node][i]==1 && visited[i]==0)
{
visited[i]=1;
path[i] = node;
//printf(" **** %d\n",node);
if(i==d)
return 1;
dist++;
insert(i);
}
}
// }
//printf("%d --> ",node);
}
while(front<=rear);
return 0;
}
void main()
{
//Declare necessary variables
int i=0,j=0,e=0,n1=0,n2=0,node=0,dest=0,source=0;
//Accept the number of nodes
printf("Enter the no of vertices : ");
scanf("%d",&v);
//Initializing the adjacent matrix
for(i=0;i<v;i++)
{
visited[i]=0;
queue[i]=0;
path[i]=0;
for(j=0;j<v;j++)
adj[i][j]=0;
}
//Accept the number edges
printf("Enter the no of edges : ");
scanf("%d",&e);
//Create the matrix
for (i=0;i<e;i++)
{
printf("Enter the end vertices of edge %d : ", i+1);
scanf("%d %d",&n1,&n2);
n1--;
n2--;
if(((n1>=0)&&(n1<v))&&(n2<v)&&(n2>=0))
{
adj[n1][n2]=1;
//adj[n2][n1]=1;
}
else
{
printf("Unavailable Vertex. Enter again\n");
i--;
}
}
//Displaying the adjacent matrix
printf("\n\nThe adjacent matrix is :\n\n \t");
for(i=0;i<v;i++)
printf(" V%d\t",i+1);
printf("\n\n");
for(i=0;i<v;i++)
{
printf(" V%d\t",i+1);
for(j=0;j<v;j++)
printf(" %d\t",adj[i][j]);
printf("\n\n");
}
printf("Enter the source : ");
scanf("%d",&source);
printf("Enter the destination : ");
scanf("%d",&dest);
//if(bfs(0)==1)
//if(visited[dest]==0)
// printf("dist does not exist between the given vertices\n");
//else
//{
if(bfs(source-1,dest-1))
{
node=dest-1;
printf("The distance is = %d\n",dist);
printer(source-1,dest-1);
}
else
printf("Path does not exist\n");
//}
}