有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];
}
};
我不知道我错在哪里。 谢谢
这是Dijkstra算法的一个文本应用程序。
给定一个节点k
,此算法将填充一个从k
到每隔一个节点的距离最小的数组,因此此数组中的最大值将是信号到达每隔一个节点所花费的总时间。
您不能仅仅使用BFS,因为一旦它已经找到了指向某个节点的任何其他路径,它就不一定会考虑指向该节点的较短路径。 Dijkstra的算法是对BFS算法的一种改进。 见此示例,假设初始节点为1,BFS和Dijkstra给出的到其他节点的距离不同: