最短路径算法中的特例

Question

我给出了一个图，其中包含 V 个顶点、E 个边、一个源顶点 s 和一个数字 m
每条边的权重等于one
我必须找到与源节点的距离小于给定数字 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.

有没有更好的方法或任何算法可以建议？

Update:-

我使用了 BFS，但在某些情况下我仍然遇到 TLE 我试图不遍历所有节点，而不仅仅是那些与源 s 的距离小于 m 的节点并存储它们在 temp
如果我的方法有误，请指正。

这是我的代码

    #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;
}

Answer 1

Dijkstra 只是 BFS，由于优先级队列，它可以在加权图上工作，但是如果你的图是未加权的，你可以只使用 BFS

最短路径算法中的特例

Special case in shortest path algorithm

algorithm

dijkstra

shortest-path