毕设网站代做一般预算多少钱,做网站什么的好,宣讲家网站支部建设,软件外包公司容易进吗目录 1 基于 Dijkstra 算法1.1 代码说明1.2 完整代码 2 基于 Floyd 算法2.1 代码说明2.2 完整代码 前言#xff1a;我在做「399. 除法求值」时#xff0c;看到了基于 Floyd 算法的解决方案#xff0c;突然想起来自己还没有做过最短路径相关的题。因此找来了「743. 网络… 目录 1 基于 Dijkstra 算法1.1 代码说明1.2 完整代码 2 基于 Floyd 算法2.1 代码说明2.2 完整代码 前言我在做「399. 除法求值」时看到了基于 Floyd 算法的解决方案突然想起来自己还没有做过最短路径相关的题。因此找来了「743. 网络延迟时间」作为练习其本质是在求解一个源点到其他各点的最短路径。 1 基于 Dijkstra 算法
假设源点为 2 \mathrm{2} 2那么手工模拟如下图所示 代码的编写在本质上就是实现上述手工模拟过程。 1.1 代码说明
为了表示两点之间没有路径我们定义两点之间的距离为无穷大
const int inf INT_MAX / 2;说明这里只是对 i n f \mathrm{inf} inf 进行定义后面才会进行使用为什么不直接定义为 i n f I N T − M A X \mathrm{inf INT_{-}MAX} infINT−MAX因为在更新距离时涉及加法操作而 I N T − M A X \mathrm{INT_{-}MAX} INT−MAX 可能让加法越界所以我们取其一半来表示无穷大。 Step1构建图
由于题目通常给出的是边的起点、终点以及权值而非存储了图结构的二维数组因此无论是 Dijkstra 算法还是 Floyd 算法我们都需要完成图的构建。代码如下
vectorvectorint graph(n 1, vectorint(n 1, inf));
for (auto t : times)graph[t[0]][t[1]] t[2];逻辑非常简单① 创建一个二维数组 g r a p h \mathrm{graph} graph② g r a p h [ i ] [ j ] \mathrm{graph[i][j]} graph[i][j] 表示边 i , j \mathrm{i, j} i,j 的权值。 说明初始时如果两点之间没有边那么认为两点之间的距离为 i n f \mathrm{inf} inf 无穷大。 Step2定义数组
vectorint dist(n 1, inf);
dist[k] 0;
vectorint used(n 1, 0);d i s t \mathrm{dist} dist 数组用于存储每一轮源点 k \mathrm{k} k 到其他点的距离 u s e d \mathrm{used} used 数组用于表明当前点是否已经被纳入集合。 说明由于 k \mathrm{k} k 到自己的距离为 0 \mathrm{0} 0因此有 d i s t [ k ] 0 \mathrm{dist[k] 0} dist[k]0为什么不直接让 u s e d [ k ] 1 \mathrm{used[k] 1} used[k]1由于在纳入每个点时都会更新源点 k \mathrm{k} k 到其他点的距离因此我们在初始时并不直接将 k \mathrm{k} k 纳入集合而是放到后面和其他点统一处理从而避免了需要在初始时更新 d i s t \mathrm{dist} dist 数组的值的问题。 Step3纳入并更新距离
for (int i 1; i n; i) {// 查找距离源点最近的点int s -1;for (int t 1; t n; t) {if (!used[t] (s -1 || dist[s] dist[t]))s t;}// 纳入该点used[s] 1;// 更新距离for (int j 1; j n; j)dist[j] min(dist[j], dist[s] graph[s][j]);
}其中 s \mathrm{s} s 用于查找当前距离源点最近的点 t \mathrm{t} t 用于遍历所有未被纳入的点。 说明由于初始时只有 d i s t [ k ] 0 \mathrm{dist[k] 0} dist[k]0而其他距离被默认为 i n f \mathrm{inf} inf 无穷大因此第一个被纳入的一定是源点 k \mathrm{k} k。 Step4返回结果
由于题目提问「需要多久才能使所有节点都收到信号」因此我们返回源点 k \mathrm{k} k 到其他点的最短距离的最大值即可。代码如下
int ans * max_element(dist.begin() 1, dist.end());
return ans inf ? -1 : ans;如果最大值是 i n f \mathrm{inf} inf那么说明源点 k \mathrm{k} k 无法到达某些点因此返回 − 1 \mathrm{-1} −1。 1.2 完整代码
int networkDelayTime(vectorvectorint times, int n, int k) {const int inf INT_MAX / 2;vectorvectorint graph(n 1, vectorint(n 1, inf));for (auto t : times)graph[t[0]][t[1]] t[2];vectorint dist(n 1, inf);dist[k] 0;vectorint used(n 1, 0);for (int i 1; i n; i) {int s -1;for (int t 1; t n; t) {if (!used[t] (s -1 || dist[s] dist[t]))s t;}used[s] 1;for (int j 1; j n; j)dist[j] min(dist[j], dist[s] graph[s][j]);}int ans * max_element(dist.begin() 1, dist.end());return ans inf ? -1 : ans;
}2 基于 Floyd 算法 说明上图只是给出一个示例并没有把整个更新过程画完整请自行脑补。 2.1 代码说明
Step1构建图与 Dijkstra 算法一致
Step2更新距离
Floyd 算法的核心不断尝试在点 i \mathrm{i} i 和点 j \mathrm{j} j 之间加入其他点 k \mathrm{k} k 作为中间点如果加入 k \mathrm{k} k 之后的距离比加入 k \mathrm{k} k 之前的距离短那么就更新点 i \mathrm{i} i 和点 j \mathrm{j} j 之间的距离。重复上述操作 n \mathrm{n} n 次即可计算出任意两点之间的最短路径。
for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (graph[i][k] 0 graph[k][j] 0)graph[i][j] graph[i][j] 0 ?min(graph[i][j], graph[i][k] graph[k][j]): graph[i][k] graph[k][j];}}
}注意中间点 k \mathrm{k} k 必须在最外层循环否则一些路径无法被更新到为什么判断条件是 0 \mathrm{ 0} 0因为题目给出的边的权值的范围为 [ 0 , 100 ] \mathrm{[0,100]} [0,100]所以需要包含 0 \mathrm{0} 0。 Step3返回结果
int ans -1;
for (int j 1; j n; j) {if (graph[k][j] -1 k ! j)return -1;else if (k ! j)ans max(ans, graph[k][j]);
}
return ans;由于我们只需要源点 k \mathrm{k} k 到其他点的距离因此只需要遍历 g r a p h \mathrm{graph} graph 中的第 k \mathrm{k} k 行。 说明由于我们在本方案中定义两点之间没有路径时的边的权值为 − 1 \mathrm{-1} −1因此只要 g r a p h [ k ] [ j ] − 1 \mathrm{graph[k][j] -1} graph[k][j]−1就说明源点 k \mathrm{k} k 无法到达点 j \mathrm{j} j因此返回 − 1 \mathrm{-1} −1。 2.2 完整代码
int networkDelayTime(vectorvectorint times, int n, int k) {vectorvectorint graph(n 1, vectorint(n 1, -1));for (auto t : times)graph[t[0]][t[1]] t[2];for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (graph[i][k] 0 graph[k][j] 0)graph[i][j] graph[i][j] 0 ?min(graph[i][j], graph[i][k] graph[k][j]): graph[i][k] graph[k][j];}}}int ans -1;for (int j 1; j n; j) {if (graph[k][j] -1 k ! j)return -1;else if (k ! j)ans max(ans, graph[k][j]);}return ans;
}虽然 Floyd 算法写起来没有 Dijkstra 算法繁琐但是针对该问题的时间复杂度更高。
