Single source shortest path by using DFS

 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