网站网页制作图片素材,企业年报网上申报入口免费官方,动态ip网站如何备案,在线企业查询系统题目链接743. 网络延迟时间 题目描述有 N 个网络节点#xff0c;标记为 1 到 N。给定一个列表 times#xff0c;表示信号经过有向边的传递时间。 times[i] (u, v, w)#xff0c;其中 u 是源节点#xff0c;v 是目标节点#xff0c; w 是一个信号从源节点传递到目标节点的…题目链接743. 网络延迟时间 题目描述有 N 个网络节点标记为 1 到 N。给定一个列表 times表示信号经过有向边的传递时间。 times[i] (u, v, w)其中 u 是源节点v 是目标节点 w 是一个信号从源节点传递到目标节点的时间。现在我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号如果不能使所有节点收到信号返回 -1。样例输入times [[2,1,1],[2,3,1],[3,4,1]], N 4, K 2输出2数据范围N 的范围在 [1, 100] 之间。K 的范围在 [1, N] 之间。times 的长度在 [1, 6000] 之间。所有的边 times[i] (u, v, w) 都有 1 u, v N 且 0 w 100。算法图论的题目一般是 3 步建图 - 图论算法 - 后处理。本题也是一样的思路先建邻接表然后求单源最短路然后根据找到的各个点的最短路找到从起始点出发可以到达的最远的距离。一般比较难的题目难点都是在建图这一步。有的是非常隐晦的图论问题想不到建图处理例如 127. 单词接龙有的是建图过程中 corner case 非常多很容易漏例如 444. 序列重建。成功完成建图之后(一般是建邻接表比较多)之后的图论算法就比较模板化了。当边的权都相同时求最短路直接一趟 BFS就可以典型题目 1091. 二进制矩阵中的最短路径。当边权不同的时候有以下几种。dijkstra 数组实现: O(E V^2)有贪心思想不能处理负权dijkstra 堆实现: O(ElogV VlogV)有贪心思想不能处理负权bellman ford: O(VE), 可以处理负权可以检测负环spfa: O(VE), bellman ford 的优化, 可以处理负权可以检测负环floyd: O(V^3) 可以把所有点之间的最短路径求出如果求多源最短路时间复杂度可摊销如果没有负权的话一般使用 dijkstra 最好。代码(c)代码框架就是 建立邻接表 - 单源最短路算法 - 后处理单源最短路算法的 5 种算法都是模板对应的实现在引申部分class Solution {
public:int networkDelayTime(vectorvectorint times, int N, int K) {vectorvectorvectorint g(N 1);for(vectorint edge: times)g[edge[0]].push_back({edge[1], edge[2]});// 求带权邻接表的最短路vectorint d dijkstra_array(g, K, N);// vectorint d dijkstra_heap(g, K, N);// vectorint d bellman_ford(g, K, N);// vectorint d spfa(g, K, N);// vectorint d floyd(g, K, N);int res 0;for(int i 1; i N; i){if(d[i] -1)return -1;res max(res, d[i]);}return res;}
};
引申: 权邻接表的单源最短路模板代码接口// g 是建好的邻接表start 是起始点N 是节点个数 返回各个点到 start 的最短路径
vectorint shortest_path(vectorvectorvectorint g, int start, int N)
5个算法的接口都一样下面是对应的模板代码原理部分没有展开。如果能够将问题转化成模板问题再套模板就轻松愉快了。这个有点类似下棋或者炒菜的背谱只会背谱肯定是不好的但是背谱可以快速下出挑不出什么毛病的棋快速炒出80分的菜。1. dijkstra 数组实现vectorint dijkstra_array(vectorvectorvectorint g, int start, int N)
{// dijkstra 数组实现 O(E V^2)// 不能有负权// 存放 start 到各个点的最短路径vectorint d(N 1, -1);d[start] 0;// 记录是否找到 start 到该点的最短路径vectorbool visited(N 1, false);visited[start] true;// 初始化 start 到各个点的距离for(vectorint son: g[start])d[son[0]] son[1];for(int cnt 1; cnt N - 1; cnt){int min_val INT_MAX / 2, min_idx 0;// 遍历所有节点找到离 start 最近的节点for(int i 1; i N; i){if(d[i] ! -1 !visited[i] d[i] min_val){min_idx i;min_val d[i];}}// 标记离 start 最近距离节点已经找到visited[min_idx] true;// 根据刚刚找到的距离 start 最短的节点// 通过该节点更新 start 与其它节点的距离for(vectorint son: g[min_idx]){if(d[son[0]] ! -1) // 之前路径与当前更新路径的最小值d[son[0]] min(d[son[0]], min_val son[1]);else // 该节点第一次访问直接更新d[son[0]] min_val son[1];}}return d;
}
2. dijkstra 堆实现vectorint dijkstra_heap(vectorvectorvectorint g, int start, int N)
{// dijkstra 堆实现 O(ElogV VlogV)// 不能有负权// 存放 start 到各个点的最短路径vectorint d(N 1, INT_MAX / 2);d[start] 0;priority_queuevectorint, vectorvectorint , Cmp pq; // 队列元素 (节点编号到 start 的距离)pq.push({start, 0});while(!pq.empty()){vectorint cur pq.top();pq.pop();if(d[cur[0]] cur[1]) continue;for(vectorint son: g[cur[0]]){if(d[son[0]] d[cur[0]] son[1]) continue;d[son[0]] d[cur[0]] son[1];pq.push({son[0], d[son[0]]});}}return d;
}struct Cmp
{bool operator() (const vectorint item1, const vectorint item2){return item1[1] item2[1]; // 最小堆}
};
3. bellman ford松弛操作它的原理是著名的定理“三角形两边之和大于第三边”vectorint bellman_ford(vectorvectorvectorint g, int start, int N)
{// bellman ford O(VE)// 可以检测负环vectorint d(N 1, -1);d[start] 0;// 进行 N - 1 轮松弛// 因为任意两点之间最短路最多包含 N - 1 条边for(int cnt 1; cnt N - 1; cnt){// u: 源节点v: 子节点, w: uv 的权for(int u 1; u N; u){if(d[u] -1) continue;for(vectorint son: g[u]){int v son[0], w son[1];// 判断能否通过 u - v 缩短 d[v] (松弛)if(d[u] w d[v] || d[v] -1)d[v] d[u] w;}}}/* 可以检测负环for(int u 1; u N; u){for(vectorint son: g[u]){int v son[0], w son[1];if(d[u] w d[v])// 有负环}}*/return d;
}
4. spfaSPFA算法的基本思想在Bellman-Ford算法中很多松弛操作其实都是没有必要的例如对于一条从 x 到 y 的边如果连 x 都还没被松弛那 y 肯定也还不能被 x 松弛。用一个队列来存储已经被松弛过的点然后用队列里的点去松弛其他点就可以避免用一个还没有被松弛的点去松弛另外的点。vectorint spfa(vectorvectorvectorint g, int start, int N)
{// 与 bellman ford 相同, O(VE)// 可以检测负环vectorint d(N 1, -1);d[start] 0;queueint, listint q;q.push(start);// 记录每个点到 start 的节点个数vectorint cnt(N 1, 0);cnt[start] 1;while(!q.empty()){int cur q.front();q.pop();for(vectorint son: g[cur]){if(d[son[0]] -1 || d[son[0]] d[cur] son[1]){cnt[son[0]] cnt[cur] 1;if(cnt[son[0]] N) return d; // 若 son 到 start 的节点个数大于 N 了说明有负环// 当最短距离发生变化且不在队列中时将该节点加入队列d[son[0]] d[cur] son[1];q.push(son[0]);}}}return d;
}
5. floydvectorint floyd(vectorvectorvectorint g, int start, int N)
{// floyd 需要邻接矩阵 O(V^3)// 可以做多源最短路vectorvectorint adj_matrix(N 1, vectorint(N 1, -1));for(int i 1; i N; i)adj_matrix[i][i] 0;for(int u 1; u N; u)for(vectorint son: g[u])adj_matrix[u][son[0]] son[1];// 遍历所有节点其中 k 是用于松弛的点for(int k 1; k N; k)for(int i 1; i N; i)for(int j 1; j N; j)// 使用 k 松弛 i - j 的最短路径if(adj_matrix[i][k] ! -1 adj_matrix[k][j] ! -1){if(adj_matrix[i][j] ! -1)adj_matrix[i][j] min(adj_matrix[i][j], adj_matrix[i][k] adj_matrix[k][j]);elseadj_matrix[i][j] adj_matrix[i][k] adj_matrix[k][j];}vectorint d(N 1, -1);for(int i 1; i N; i)d[i] adj_matrix[start][i];return d;
}
