shortest path algorithm with unit weight

Solutions on MaxInterview for shortest path algorithm with unit weight by the best coders in the world

showing results for - "shortest path algorithm with unit weight"
Simon
25 Jan 2019
1//Shortest Path in Undirected graph using Unit weight BFS
2//Check the striver graph series
3#include<bits/stdc++.h>
4using namespace std;
5void addedge(vector<int>adj[],int u,int v)
6{
7    adj[u].push_back(v);
8    adj[v].push_back(u);
9}
10void shortest(vector<int>adj[],int n , int source)
11{
12    int distance[n];
13    for(int i=0;i<n;i++)
14    {
15        distance[i]=INT_MAX;
16    }
17    queue<int>q;
18    distance[source]=0;
19    q.push(source);
20    while(!q.empty())
21    {
22        int node=q.front();
23        q.pop();
24        for(auto j:adj[node])
25        {
26            if(distance[node]+1<distance[j])
27            {
28                distance[j]=distance[node]+1;
29                q.push(j);
30            }
31        }
32    }
33    for(int i=0;i<n;i++)
34    {
35        cout<<distance[i]<<" ";
36    }
37}
38int main()
39{
40    int vertex,edges;
41    cout<<"Enter the number of vertex and edges:"<<endl;
42    cin>>vertex>>edges;
43    vector<int>adj[vertex];
44    int a,b;
45    cout<<"Enter the links:"<<endl;
46    for(int i=0;i<edges;i++)
47    {
48        cin>>a>>b;
49        addedge(adj,a,b);
50    }
51    int value;
52    cout<<"Enter the node from which you want to calculate the shortest distance:"<<endl;
53    cin>>value;
54    shortest(adj,vertex,value);
55    return 0;
56}
57