企业官网建设流程全解析

网站开发一定找前端么,如果将域名指向网站,网站关键词库是怎么做的,python 做网站 案例目录 前言 一、前置知识#xff1a;多源最短路与 Floyd 算法的核心定位 1. 什么是多源最短路#xff1f; 2. 为什么选择 Floyd 算法#xff1f; 3. 关键前提#xff1a;Floyd 算法的适用条件 4. 核心思想#xff1a;动态规划与 “插点法” 空间优化#xff1a;从三…目录前言一、前置知识多源最短路与 Floyd 算法的核心定位1. 什么是多源最短路2. 为什么选择 Floyd 算法3. 关键前提Floyd 算法的适用条件4. 核心思想动态规划与 “插点法”空间优化从三维到二维5. 算法流程总结二、Floyd 算法的代码实现简洁到极致1. 基础模板代码无向图2. 有向图的修改3. 关键细节说明三、模板题实战洛谷 B3647 【模板】Floyd题目链接题目描述输入描述输出描述示例输入示例输出解题思路完整 C 代码代码解释四、基础应用洛谷 P2910 Clear And Present Danger题目链接题目描述输入描述示例输入示例输出解题思路完整 C 代码代码解释五、进阶实战洛谷 P1119 灾后重建题目链接题目描述输入描述示例输入示例输出解题思路关键观察算法设计为什么这样可行完整 C 代码代码解释六、拓展应用洛谷 P6175 无向图的最小环问题题目链接题目描述输入描述示例输入示例输出解题思路核心观察算法设计关键细节完整 C 代码代码解释七、Floyd 算法的优化与注意事项1. 空间优化2. 避免溢出3. 处理重边和自环4. 负环的检测总结前言在图论的应用场景中我们常常会遇到这样的需求地图应用中查询任意两个城市间的最短车程、网络拓扑中计算任意两台设备间的最优传输路径、物流规划中确定任意两个仓库间的最低运输成本…… 这些问题的核心都是多源最短路—— 即求出图中每一对顶点之间的最短路径。单源最短路解决的是 “从一个起点到所有其他点” 的路径问题而多源最短路则需要覆盖 “所有点到所有点” 的全量路径。今天这篇文章我会聚焦多源最短路的经典解法 ——Floyd-Warshall 算法简称 Floyd 算法从原理剖析、代码实现到实战例题带你彻底掌握这一 “通吃所有点对” 的强大算法。不仅如此我还会分享 Floyd 算法的核心拓展应用如无向图最小环问题、动态加点的最短路径查询结合洛谷经典例题让你从 “理解算法” 到 “灵活运用”真正吃透多源最短路问题下面就让我们正式开始吧一、前置知识多源最短路与 Floyd 算法的核心定位在正式讲解算法之前我们先明确几个关键概念帮你建立对多源最短路的清晰认知1. 什么是多源最短路多源最短路的定义很简单给定一个带权图有向或无向边权可正可负但不能存在负环否则部分点对的最短路径不存在求出所有顶点对 (i, j)之间的最短路径长度i 到 j 的最短路径以及 j 到 i 的最短路径若图为有向图则可能不同。2. 为什么选择 Floyd 算法解决多源最短路其实有两种思路思路 1对每个顶点都跑一遍单源最短路算法如 Dijkstra 或 SPFA。若图中有 n 个顶点时间复杂度为 O (n×(m log n))堆优化 Dijkstra适用于稀疏图。思路 2使用 Floyd 算法时间复杂度为 O (n³)适用于稠密图n 较小如 n≤200。Floyd 算法的核心优势在于实现简单、代码简洁仅需三层循环即可完成无需复杂的数据结构支持。对于 n≤200 的场景O (n³) 的时间复杂度完全可接受200³8e6计算机可瞬间处理因此成为多源最短路的首选算法。3. 关键前提Floyd 算法的适用条件Floyd 算法虽然强大但有一个重要前提图中不能存在负环。因为如果存在负环那么经过负环的点对之间的路径长度可以无限减小不存在最短路径。但要注意Floyd 算法支持负权边只要没有负环。例如图中存在边权为 - 2、-3 的边只要没有形成回路的边权和为负就可以正常计算。4. 核心思想动态规划与 “插点法”Floyd 算法的本质是动态规划其核心思想可以概括为 “插点法”—— 通过不断在两个顶点之间插入新的顶点更新这两个顶点之间的最短路径。我们用一个三维数组f[k][i][j]来表示动态规划的状态状态定义f[k][i][j]表示 “仅允许经过顶点 1~k 作为中转点时顶点 i 到顶点 j 的最短路径长度”。基于这个状态定义我们可以得到状态转移方程当不使用顶点 k 作为中转点时f[k][i][j] f[k-1][i][j]最短路径还是原来的路径当使用顶点 k 作为中转点时f[k][i][j] min(f[k-1][i][k] f[k-1][k][j], f[k-1][i][j])比较 “直接从 i 到 j” 和 “i 经过 k 到 j” 的路径长度取较小值。空间优化从三维到二维观察状态转移方程可以发现f[k][i][j]只依赖于f[k-1][...]上一层的状态因此我们可以将三维数组优化为二维数组f[i][j]直接在原数组上进行更新。优化后的状态转移方程为f[i][j] min(f[i][j], f[i][k] f[k][j])这里的k是 “当前允许使用的中转顶点”因此循环顺序必须是先枚举 k再枚举 i 和 j—— 这是 Floyd 算法的关键细节也是最容易出错的地方5. 算法流程总结Floyd 算法的流程非常简洁总共分为 3 步初始化创建二维数组ff[i][j]表示顶点 i 到顶点 j 的初始距离。若 i j则f[i][j] 0自己到自己的距离为 0若 i 和 j 之间有直接边权值为 w则f[i][j] w若 i 和 j 之间没有直接边则f[i][j] INFINF 表示无穷大代表初始时不可达。插点更新枚举所有可能的中转顶点 k1~n然后枚举所有顶点对 (i, j)用f[i][k] f[k][j]更新f[i][j]。结果输出f[i][j]即为顶点 i 到顶点 j 的最短路径长度若仍为 INF则表示不可达。二、Floyd 算法的代码实现简洁到极致基于上述思路我们可以写出 Floyd 算法的 C 代码。代码非常简洁核心仅需三层循环适合记忆和默写。1. 基础模板代码无向图#include iostream #include cstring using namespace std; const int N 110; // 顶点数上限根据题目调整 const int INF 0x3f3f3f3f; // 表示无穷大注意避免溢出 int n, m; int f[N][N]; // f[i][j]i到j的最短路径长度 void floyd() { // 枚举中转顶点k for (int k 1; k n; k) { // 枚举所有顶点对(i, j) for (int i 1; i n; i) { for (int j 1; j n; j) { // 状态转移用k更新i到j的最短路径 f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } int main() { cin n m; // 1. 初始化f数组 memset(f, 0x3f, sizeof f); // 所有边初始化为无穷大 for (int i 1; i n; i) { f[i][i] 0; // 自己到自己的距离为0 } // 2. 读入边的信息无向图双向赋值 for (int i 0; i m; i) { int u, v, w; cin u v w; // 若存在重边取权值最小的边 f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); } // 3. 执行Floyd算法 floyd(); // 4. 输出所有点对的最短路径 for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][j] INF) { cout INF ; // 不可达 } else { cout f[i][j] ; } } cout endl; } return 0; }2. 有向图的修改如果图是有向图只需修改边的初始化部分 —— 仅需赋值f[u][v] min(f[u][v], w)无需赋值f[v][u]因为有向边的方向是单向的。修改后的边初始化代码// 读入有向边u→v权值w for (int i 0; i m; i) { int u, v, w; cin u v w; f[u][v] min(f[u][v], w); // 仅单向赋值 }3. 关键细节说明无穷大的选择使用0x3f3f3f3f作为无穷大原因是它是一个较大的数约 1e9不会被正常的边权值超过两个0x3f3f3f3f相加不会溢出0x3f3f3f3f * 2 0x7ffffffe小于 int 的最大值0x7fffffff。重边处理如果图中存在重边多个边连接同一对顶点我们取权值最小的边因此用min(f[u][v], w)赋值。循环顺序必须先枚举中转顶点 k再枚举 i 和 j如果顺序错误会导致部分路径无法正确更新。三、模板题实战洛谷 B3647 【模板】Floyd题目链接B3647 【模板】Floyd题目描述给出一张由n个点m条边组成的无向图求出所有点对(i, j)之间的最短路径。输入描述第一行两个整数n、m分别表示顶点数和边数接下来m行每行三个整数u、v、w表示顶点u和v之间有一条权值为w的无向边。输出描述输出n行每行n个整数第i行第j个整数表示顶点i到j的最短路径长度。示例输入4 4 1 2 1 2 3 1 3 4 1 4 1 1示例输出0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0解题思路这是 Floyd 算法的基础模板题无向图可看作双向有向图因此读入边时需同时更新f[u][v]和f[v][u]。直接套用 Floyd 算法框架即可。完整 C 代码#include iostream #include cstring using namespace std; const int N 110; const int INF 0x3f3f3f3f; int n, m; int f[N][N]; int main() { // 初始化f数组 memset(f, 0x3f, sizeof f); for (int i 1; i N; i) { f[i][i] 0; } // 读入数据 cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; // 无向边双向更新保留最小权值避免重边 f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); } // Floyd核心算法 for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } // 输出结果 for (int i 1; i n; i) { for (int j 1; j n; j) { cout f[i][j] ; } cout endl; } return 0; }代码解释初始化时f[i][i] 0其余为INF无向边需双向更新避免重边影响取最小权值三层循环严格按照k → i → j的顺序确保每个中间顶点都能正确更新路径输出时直接打印f[i][j]即为i到j的最短路径长度。四、基础应用洛谷 P2910 Clear And Present Danger题目链接P2910 [USACO08OPEN] Clear And Present Danger S题目描述农夫约翰驾驶小艇在海上航行海上有N个岛屿编号 1~N。约翰需要按照藏宝图上的序列A₁, A₂, ..., Aₘ依次经过这些岛屿从A₁出发最后到Aₘ求经过的航线危险指数之和的最小值。危险指数D[i][j]表示岛屿i到j的直接航线危险指数题目已给出所有D[i][j]。输入描述第一行两个整数N、M分别表示岛屿数和必须经过的岛屿序列长度接下来M行每行一个整数Aᵢ表示必须经过的第i个岛屿接下来N行每行N个整数第i行第j个整数表示D[i][j]D[i][i] 0。示例输入3 4 1 2 1 3 0 5 1 5 0 2 1 2 0示例输出7解题思路题目给出的D[i][j]是直接航线的危险指数但可能存在经过其他岛屿的更短路径危险指数更小因此需要先通过 Floyd 算法求出所有岛屿对之间的最短危险指数即任意两个岛屿之间的最优路径然后按照序列A₁ → A₂ → ... → Aₘ累加相邻岛屿的最短危险指数之和即为答案。完整 C 代码#include iostream #include cstring typedef long long LL; // 防止结果溢出 using namespace std; const int N 110; const int INF 0x3f3f3f3f; int n, m; int f[N][N]; int a[10010]; // 存储必须经过的岛屿序列M最大为1e4 int main() { // 读入岛屿数和序列长度 cin n m; // 读入必须经过的岛屿序列 for (int i 1; i m; i) { cin a[i]; } // 读入初始危险指数矩阵D[i][j]并初始化f数组 for (int i 1; i n; i) { for (int j 1; j n; j) { cin f[i][j]; } } // Floyd算法求所有岛屿对的最短危险指数 for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } // 累加序列中相邻岛屿的最短危险指数之和 LL res 0; for (int i 2; i m; i) { int u a[i-1], v a[i]; res f[u][v]; } // 输出结果 cout res endl; return 0; }代码解释由于M最大为 1e4N最大为 100f[i][j]最大为 1e5累加和可能超过 int 范围因此用long long存储结果初始时f[i][j]直接赋值为题目给出的D[i][j]无需额外初始化题目已保证D[i][i] 0累加过程中直接使用 Floyd 更新后的f[u][v]u和v为序列中相邻岛屿确保每一段都是最优路径。五、进阶实战洛谷 P1119 灾后重建题目链接P1119 灾后重建题目描述B 地区有N个村庄编号 0~N-1M条双向公路。每个村庄i有一个重建完成时间t[i]t[i]为 0 表示初始即可通车重建完成当天即可通车。有Q个询问(x, y, t)询问在第t天村庄x到y的最短路径长度路径必须经过已重建完成的村庄。若无法到达如x或y未重建、无路径输出-1。输入描述第一行两个整数N、M表示村庄数和公路数第二行N个非负整数t[0], t[1], ..., t[N-1]表示每个村庄的重建时间保证t非递减接下来M行每行三个整数i、j、w表示村庄i和j之间有一条长度为w的公路接下来一行整数Q表示询问数接下来Q行每行三个整数x、y、t表示询问保证t非递减。示例输入4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4示例输出-1 -1 5 4解题思路这道题是 Floyd 算法的经典进阶应用核心在于理解 “重建时间” 对路径的限制 —— 只有重建完成的村庄才能作为中间顶点或路径上的顶点。关键观察村庄的重建时间t是非递减的t[0] ≤ t[1] ≤ ... ≤ t[N-1]询问的时间t也是非递减的Floyd 算法的 “插点法” 本质是依次将顶点作为中间顶点加入更新路径。这与 “村庄按重建时间依次通车” 的过程完全契合算法设计初始化 Floyd 数组f公路初始长度为给定w无公路为INFf[i][i] 0维护一个指针pos表示当前已重建完成的村庄初始pos 0对于每个询问(x, y, t)a. 先将所有重建时间≤ t的村庄t[pos] ≤ t作为中间顶点加入 Floyd 算法更新路径因为这些村庄已通车可作为中转b. 检查x和y是否已重建t[x] ≤ t且t[y] ≤ tc. 若已重建且f[x][y] ! INF输出f[x][y]否则输出-1。为什么这样可行由于村庄重建时间和询问时间都是非递减的一旦某个村庄被加入作为中间顶点后续的询问都可以使用它无需重复处理每次询问前只需要处理新增的已重建村庄避免了重复计算时间复杂度优化为O(Q N² M)因为每个村庄最多被处理一次每次处理O(N²)。完整 C 代码#include iostream #include cstring using namespace std; const int N 210; const int INF 0x3f3f3f3f; int n, m, q; int t[N]; // 每个村庄的重建时间 int f[N][N]; // Floyd数组 // 加入村庄k作为中间顶点更新所有路径 void floyd(int k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } int main() { // 初始化Floyd数组 memset(f, 0x3f, sizeof f); for (int i 0; i N; i) { f[i][i] 0; } // 读入村庄数和公路数 cin n m; // 读入每个村庄的重建时间 for (int i 0; i n; i) { cin t[i]; } // 读入公路信息 for (int i 0; i m; i) { int u, v, w; cin u v w; f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); // 无向公路双向更新 } // 读入询问数 cin q; int pos 0; // 当前已处理的最后一个村庄已重建完成 while (q--) { int x, y, time; cin x y time; // 将所有重建时间≤当前询问时间的村庄加入Floyd while (pos n t[pos] time) { floyd(pos); pos; } // 检查x和y是否已重建且存在路径 if (t[x] time || t[y] time || f[x][y] INF) { cout -1 endl; } else { cout f[x][y] endl; } } return 0; }代码解释村庄编号从 0 开始与题目一致因此数组初始化和循环均从 0 开始floyd(k)函数的作用是将村庄k作为中间顶点更新所有顶点对的最短路径指针pos的作用是 “懒加载” 已重建的村庄避免重复处理优化时间复杂度询问处理时先确保所有已重建的村庄都被作为中间顶点加入再判断路径是否存在。六、拓展应用洛谷 P6175 无向图的最小环问题题目链接P6175 无向图的最小环问题题目描述给定一张无向图求图中一个至少包含 3 个顶点的环使得环上所有边的权值之和最小即最小环。若无环输出No solution.。输入描述第一行两个整数n、m表示顶点数和边数接下来m行每行三个整数u、v、d表示顶点u和v之间有一条权值为d的无向边。示例输入5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20示例输出61解题思路最小环问题是多源最短路的经典拓展Floyd 算法可以巧妙地解决这个问题。核心观察无向图中的最小环必然可以表示为i → ... → k → j → i其中k是环中编号最大的顶点i和j是环中与k直接相连的两个顶点i → ... → j的路径中不包含k因为k是最大编号顶点因此这条路径的最短长度就是f[k-1][i][j]只允许经过顶点 1~k-1 时的最短路径。因此最小环的长度可以表示为f[k-1][i][j] w[i][k] w[k][j]其中w[i][k]是i到k的直接边权w[k][j]是k到j的直接边权。算法设计初始化 Floyd 数组f和原始边权数组ww[i][j]存储i到j的直接边权枚举中间顶点k从 1 到 na. 在更新f[k][i][j]之前先枚举所有i k、j k、i ! j计算f[k-1][i][j] w[i][k] w[k][j]并更新最小环长度b. 然后正常执行 Floyd 的状态转移更新f[k][i][j]枚举结束后若最小环长度仍为无穷大输出No solution.否则输出最小环长度。关键细节必须在更新f[k][i][j]之前计算最小环因为此时f[i][j]仍保持着“只允许经过 1~k-1”的状态原始边权数组w需要单独保存不能被 Floyd 更新覆盖因为w[i][k]是i到k的直接边权而非最短路径。完整 C 代码#include iostream #include cstring using namespace std; const int N 110; const int INF 1e8; // 无穷大避免溢出 int n, m; int f[N][N]; // Floyd数组存储最短路径 int w[N][N]; // 原始边权数组存储直接边权 int min_cycle INF; // 最小环长度 int main() { // 初始化f和w数组 for (int i 1; i N; i) { for (int j 1; j N; j) { f[i][j] w[i][j] INF; } f[i][i] w[i][i] 0; } // 读入顶点数和边数 cin n m; for (int i 0; i m; i) { int u, v, d; cin u v d; // 无向边双向更新保留最小边权避免重边 w[u][v] w[v][u] min(w[u][v], d); f[u][v] f[v][u] min(f[u][v], d); } // Floyd算法求最短路径并同时找最小环 for (int k 1; k n; k) { // 步骤1找包含k的最小环k是环中最大编号顶点 for (int i 1; i k; i) { for (int j i 1; j k; j) { // 环的长度 i到j的最短路径不经过k i到k的直接边 k到j的直接边 if (f[i][j] ! INF w[i][k] ! INF w[k][j] ! INF) { min_cycle min(min_cycle, f[i][j] w[i][k] w[k][j]); } } } // 步骤2正常更新Floyd数组插入k作为中间顶点 for (int i 1; i n; i) { for (int j 1; j n; j) { if (f[i][k] ! INF f[k][j] ! INF) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } } // 输出结果 if (min_cycle INF) { cout No solution. endl; } else { cout min_cycle endl; } return 0; }代码解释单独维护w数组存储原始边权避免被 Floyd 更新覆盖枚举k时先找包含k的最小环i k、j k确保k是环中最大编号顶点再更新 Floyd 数组最小环的长度是i→j的最短路径不经过k加上i→k和k→j的直接边权确保环的完整性和最小性。七、Floyd 算法的优化与注意事项1. 空间优化Floyd 算法的空间复杂度是O(n²)对于n1000的场景n²1e6内存占用约 4MBint 类型完全可以接受但对于n1e4n²1e8内存占用约 400MB会超出内存限制。此时可以考虑若只需查询部分顶点对的最短路径可使用多源 Dijkstra对每个顶点跑一次 Dijkstra对于稀疏图多源 Dijkstra 的时间复杂度O(n m log n)可能优于 Floyd 的O(n³)。2. 避免溢出无穷大INF的取值要合适不能太大否则INF INF会溢出也不能太小否则会与实际边权冲突。通常取0x3f3f3f3f约 1e9因为0x3f3f3f3f 0x3f3f3f3f 2e9小于 int 的最大值2^31-12147483647若边权较大或顶点数较多需用long long存储f[i][j]避免累加和溢出。3. 处理重边和自环重边保留权值最小的边如w[u][v] min(w[u][v], d)自环由于f[i][i] 0自环的边权不会影响最短路径因为i→i的最短路径长度为 0因此可以忽略自环或在初始化时不处理自环。4. 负环的检测Floyd 算法本身无法直接检测负环但可以通过以下方法判断运行 Floyd 算法后若存在f[i][i] 0则说明顶点i在一个负环上因为自己到自己的最短路径长度为负数存在负环若只需检测是否存在负环建议使用 Bellman-Ford 或 SPFA 算法效率更高。总结Floyd 算法是多源最短路的核心算法代码简洁、思想巧妙虽然时间复杂度为O(n³)但在顶点数较小的场景n ≤ 200中效率很高且能处理有向图、无向图、带权图非负权或负权无负环等多种情况。Floyd 算法虽然简单但蕴含的动态规划思想和 “插点法” 技巧值得深入思考。希望通过本文的学习你能彻底掌握多源最短路问题并能灵活应对各类实战场景如果有任何疑问或问题欢迎在评论区交流讨论