0

I have given a graph with V vertices, E edges, a source vertex s and a number m
The weight of each edge is equal to one
I have to find the shortest path to all those nodes whose distance from the source node is lesser than given number m

My approach:- I used Dijkstra algorithm and find a path for all nodes and then selected those nodes whose distance is less than m but I am getting Time limit exceed.

Is there any better approach or any algorithm anyone can suggest?

Update:-

I used BFS but still, I am getting TLE on some cases I am trying not to transverse all nodes rather than only those whose distance is less than m from source s and storing them in temp
Please correct me if my approach is wrong.

Here is my code

    #include <bits/stdc++.h>

    using namespace std;

    const long long N = 5*1e4;
    const long long W = 1e9;
    const long long INF = 1e9;
    vector<long long> g[N];                //graph 
    long long dist[N];                     //distance
    bool visited[N];                       // is node visited or  not
    void shortest_path(long long s,long long m){
            fill(dist, dist + N, INF);
            fill(visited, visited + N, 0);
            dist[s] = 0;
            vector<int>temp;    
            queue<long long>q;              //Queue
            q.push(s);
            while(!q.empty())
                {
                    long long v = q.front();
                    q.pop();
                    if(visited[v]) continue;
                    visited[v] = 1;
                    temp.push_back(v);       //storing nodes in temp
                    for(auto it: g[v])
                    {
                        long long u = it;
                        if(dist[v] + 1<= m)  // nodes those distance is less than m
                        {
                            dist[u] = dist[v] + 1;
                            q.push(u);
                        }
                    }
                }
               for(int i=0;i<temp.size();i++){
                        cout<<temp[i]<<" ";
                  }
    }
int main()
{
        long long n;
        cin>>n;
        for(long long i = 0; i < n; ++i) g[i].clear();
        for(long long i = 0; i < n-1; i++)
        {
            long long u,v;
            cin>>u>>v;
            u--;v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        long long q;
        cin>>q;
        for(long long i=0;i<q;i++){
            long long s,m;
            cin>>s>>m;
            s--;
            shortest_path(s,m);
             cout<<endl;
        }
    return 0;
}
1
  • 2
    The weight of each edge is equal to one -> use bfs, not dijstra Commented Jun 24, 2018 at 16:33

1 Answer 1

1

Dijkstra's is just BFS that works on weighted graphs thanks to a priority queue, but if your graph is unweighted you can just use BFS

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.