What is single source shortest path:- Finding the length of the shortest path between source vertex and all the vertex.
Code:-
#include<bits/stdc++.h>
using namespace std;
vector<int> arr[100];
int visited[100];
int dis[100]; // for distance
// function for dfs
void dfs(int n,int d)
{
visited[n]=1;
dis[n]=d;
for(int child:arr[n])
{
if(visited[child]==0)
dfs(child,d+1);
}
}
//Driver program
int main()
{
int n;
cout<<"Enter the number of vertex"<<endl;
cin>>n;
int a,b;
cout<<"Enter the "<<n-1<<" Edges"<<endl;
for(int i=0;i<n-1;i++)
{
cin>>a>>b;
arr[a].push_back(b);
arr[b].push_back(a);
}
cout<<"Enter the source vertex"<<endl;
cin>>a;
// function calling
dfs(a,0);
cout<<"Distance of all the vertex with the source vetex "<<a<<endl;
for(int i=1;i<=n;i++)
{
cout<<i<<" : "<<dis[i]<<endl;
}
return 0;
}
output:-
For this graph
Enter the number of vertex
6
Enter the 5 edges
1 2
2 3
2 4
4 5
4 6
Enter the source vertex
1
Distance of all the vertex from the source vertex 1
1 : 0
2 : 1
3 : 2
4 : 2
5 : 3
6 : 3
0 Comments