本文主要是介绍743. 网络延迟时间（最短路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2注意:
N的范围在[1, 100]之间。K的范围在[1, N]之间。times的长度在[1, 6000]之间。- 所有的边
times[i] = (u, v, w)都有1 <= u, v <= N且0 <= w <= 100。
思路：这题目是一个有向图求最短路径的问题，求出K点到每一个点到最短路径，然后取其中最大的一个就是需要的时间了。
采用Dijkstra算法来求有向图的最短路径。
1、先回顾一下Dijkstra算法原理。
2、Dijkstra算法伪代码：
//G为图，S，U，K为起点
Dijkstra(G, U, S)
{初始化;for(循环n次，每次向S中添加一个顶点){uu = 去U中找出路径最小的顶点的标号;在U中删掉uu，并且将uu将入到S中for(在U中遍历从uu出发能到达的所有顶点v){if(以uu为中介点使s到顶点v的最短距离d[v]更优){优化d[v];}}}
}3、设计Dijkstra算法所用到的数据结构：
数据结构的设计应该有很多种方法，我就选了一种最朴素的：
用两个vector表示S和U，每个vector里面索引值存顶点，元素值存源点到该顶点的路径长度。
另外，考虑到数组中删除元素代价比较大，所以我额外建了一个标记数组visited，用来标记U中被移除的顶点。
4、最后，代码实现一下：
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int N, int K) {//定义并初始化S，U，visitedvector<int>S(N+1, INT_MAX), U=S;vector<bool>v(N+1, true);U[K]=0;//每次处理掉一个顶点for(int c=1; c<=N; ++c){//去U中找最小路径int uu=0;for(int i=1; i<=N; ++i){if(v[i] && U[i]<U[uu])uu=i;}//在U中删掉uu，并且将uu将入到S中v[uu]=false;S[uu]=U[uu];//在U中遍历(要求该点在v中的值为true)从uu出发能到达的所有顶点v(从题目中给的G下手)for(auto x:times){if(x[0]==uu && v[x[1]] && S[uu]+x[2]<U[x[1]]){//以uu为中介点使s到顶点v的最短距离d[v]更优U[x[1]]=S[uu]+x[2];}}}//此时S中存的应该是K到每一个顶点的最短路径了//去S中找出最大值int re=0;for(int i=1; i<=N; ++i){//注意要从第一个元素算起re=max(re, S[i]);}return re==INT_MAX ?-1:re;//有可能有的点找不到最短路径}
};
这篇关于743. 网络延迟时间（最短路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
