提问者:小点点

BFS解对网络时间问题的错误回答


有N个网络节点,标记为1到N。

给定时间,作为有向边的传播时间列表times[i]=(u,v,w),其中u是源节点,v是目标节点,w是信号从源传播到目标所需的时间。

现在,我们从某个节点K发送信号,所有节点接收信号需要多长时间? 如果不可能,返回-1。

这是我的代码。 然而,它给出了错误的答案

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        
        vector<int>time(N+1);
        vector<int>visited(N+1,0);
        vector<vector<pair<int,int>>>graph(N+1);
        for(int i=0;i<times.size();i++)
        {
            graph[times[i][0]].push_back(make_pair(times[i][1],times[i][2]));
        }
        
        queue<pair<int,int>>q;
        q.push(make_pair(K,0));
        visited[K]=1;
        time[K]=0;
        while(!q.empty())
        {
            int end=q.front().first;
            int duration=q.front().second;
            q.pop();
            for(auto k:graph[end])
            {
                int first=k.first;
                int second=k.second;
                if(!visited[first])
                {
                    q.push(make_pair(first,second));
                    time[first]=duration+second;
                    visited[first]=1;
                }
                else
                {
                    time[first]=min(time[first],(duration+second));
                }
            }
        }
        for(int i=1;i<=N;i++)
        {
            if(visited[i] == 0)
            {
                return -1;
            }
        }
        sort(time.begin(),time.end());
        return time[N];
    }
};

我不知道我错在哪里。 谢谢


共1个答案

匿名用户

这是Dijkstra算法的一个文本应用程序。

给定一个节点k,此算法将填充一个从k到每隔一个节点的距离最小的数组,因此此数组中的最大值将是信号到达每隔一个节点所花费的总时间。

您不能仅仅使用BFS,因为一旦它已经找到了指向某个节点的任何其他路径,它就不一定会考虑指向该节点的较短路径。 Dijkstra的算法是对BFS算法的一种改进。 见此示例,假设初始节点为1,BFS和Dijkstra给出的到其他节点的距离不同: