编辑
从并查集到最小生成树，从拓扑排序到最短路径。
....
群星璀璨😉
编辑
- 并查集
- 最小生成树
- Prim算法
- Kruskal算法
- 拓扑排序（kahn算法）
- ·最短路径
- Dijkstra算法
- Dijkstra朴素
- Dijkstra堆优化
- Bellman_ford算法
- Bellman_ford朴素
- SPFA
- Bellman_ford之判断负权回路
- Bellman_ford之单源有限最短路
- Floyed算法
- 启发式搜索A*算法
一、并查集
编辑
作用：
- 连通性判断（两个节点是否连通）
- 检测环（在无项图中，添加两个节点是否属于同一父节点）
- 最小生成树（KrusKal）
模版：
基础应用
简单例子； 无向图，有1~5这5个节点 1 2 2 3 3 4 求解，2与4是否连通。2与5呢？ 加入1-4 是否会成环？ 按照模板给出讲解顺序 // 这只是无向图中的应用，是最基础的 // 有向图会麻烦一点点
编辑
压缩路径：
（最基础、最常用）
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; } } // 并查集里寻根的过程 int find(int u) { return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩 } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u = find(u); v = find(v); return u == v; } // 将v->u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; }
按秩合并：
（大规模场景，需要性能优化时，会用到这个）（我没遇到，不知道）
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int> father = vector<int> (n, 0); // C++里的一种数组结构 vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1 // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; rank[i] = 1; // 也可以不写 } } // 并查集里寻根的过程 int find(int u) { return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩 } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u = find(u); v = find(v); return u == v; } // 将v->u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树 else father[v] = u; if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <= }
竞赛模板（路径压缩+按秩合并结合）
单一的路径压缩 与 按秩合并 没有谁好谁坏，他们两者是互补的，之后结合之后，才能使并查集优化的最好。
#include <vector> class UnionFind { private: std::vector<int> parent; std::vector<int> rank; // 秩（树高度的上界） int count; // 连通分量个数 public: UnionFind(int n) : count(n) { parent.resize(n); rank.resize(n, 0); for (int i = 0; i < n; ++i) { parent[i] = i; } } int find(int x) { // 路径压缩：在查找过程中将节点直接连接到根节点 if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 按秩合并：将秩较小的树合并到秩较大的树 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; // 秩相同时，合并后秩增加1 } count--; } bool connected(int x, int y) { return find(x) == find(y); } int getCount() { return count; } };
使用说明：
- 初始化：创建大小为
n的并查集，每个元素初始独立成集合- find(x)：查找
x的根节点，同时进行路径压缩- unite(x, y)：合并
x和y所在的集合，按秩保持树结构平衡- connected(x, y)：判断
x和y是否属于同一集合- getCount()：返回当前连通分量（集合）的数量
特点：
- ⚡ 高效：近似常数时间复杂度（阿克曼函数的反函数）
- 📦 紧凑：仅使用两个数组存储状态
- 🏆 竞赛友好：直接用于需要并查集的算法题目
典型应用场景：
- 最小生成树（Kruskal算法）
- 动态连通性问题
- 图的连通分量统计
- 最近公共祖先（LCA）等
使用时，只需要初始化一个类，然后调用，就可以了
二、最小生成树
基础定义：
给一个无向连通图，找到一个子图，满足：
- 包含所有顶点（N个顶点）
- 有N-1条边
- 边权值最小
（举例详细解释一下）
prime是以点为基础，所以更适合稠密图（O(N^2)）
Kruskal以边为基础，更适合稀疏图 (O(nlogn))
（一般题目会这样出题：有多个城市之间埔公路(A、B、C、D)，求如何才能用最少的原材料，让所有城市之间连通？）
编辑
Prim算法：
核心思想：
从顶点出发的贪心思想，
每次循环都会连接一个 距离生成树 距离最近 的节点。
基础应用
编辑
模板：
三步走：
- 找出距离已得到生成树最近的节点。
- 更新去重数组
- 更新未加入生成树节点，到达生成树的最小距离。（用新加入的节点表示）
编辑
#include<iostream> #include<vector> #include <climits> using namespace std; int main() { int v, e; int x, y, k; cin >> v >> e; // 填一个默认最大值，题目描述val最大为10000 vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001)); while (e--) { cin >> x >> y >> k; // 因为是双向图，所以两个方向都要填上 grid[x][y] = k; grid[y][x] = k; } // 所有节点到最小生成树的最小距离 vector<int> minDist(v + 1, 10001); // 这个节点是否在树里 vector<bool> isInTree(v + 1, false); // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起 for (int i = 1; i < v; i++) { // 1、prim三部曲，第一步：选距离生成树最近节点 int cur = -1; // 选中哪个节点 加入最小生成树 int minVal = INT_MAX; for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始 // 选取最小生成树节点的条件： // （1）不在最小生成树里 // （2）距离最小生成树最近的节点 if (!isInTree[j] && minDist[j] < minVal) { minVal = minDist[j]; cur = j; } } // 2、prim三部曲，第二步：最近节点（cur）加入生成树 isInTree[cur] = true; // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组） // cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下 // 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢 for (int j = 1; j <= v; j++) { // 更新的条件： // （1）节点是 非生成树里的节点 // （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小 // 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了 if (!isInTree[j] && grid[cur][j] < minDist[j]) { minDist[j] = grid[cur][j]; } } } // 统计结果 int result = 0; for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边 result += minDist[i]; } cout << result << endl; }
Kruskal算法：
（克鲁斯卡尔算法）
核心思想：
从 “边” 开始的，贪心思想。
基础应用：
编辑
初始数据 7 11 // 7个节点、11条边 1 2 1 // 顶点1与顶点2相连、权值为1 1 3 1 1 5 2 2 6 1 2 4 2 2 3 2 3 4 1 4 5 1 5 6 2 5 7 1 6 7 1 求解最小生成树，权值最小为多少。可以转化为： （有多个城市之间埔公路，求如何才能用最少的原材料，让所有城市之间连通？） // 排序过后的 1 2 1 1 3 1 2 6 1 3 4 1 4 5 1 6 7 1 5 7 1 2 3 2 1 5 2 2 4 2 5 6 2
模板：
编辑
重点步骤：
- 储存每条边，并按照权值大小按照升序排序，放在edges数组中
- 建立并查集模板
- 通过edges数组，建立最小生成树
#include <iostream> #include <vector> #include <algorithm> using namespace std; // l,r为 边两边的节点，val为边的数值 struct Edge { int l, r, val; }; // 节点数量 int n = 10001; // 并查集标记节点关系的数组 vector<int> father(n, -1); // 节点编号是从1开始的，n要大一些 // 并查集初始化 void init() { for (int i = 0; i < n; ++i) { father[i] = i; } } // 并查集的查找操作 int find(int u) { return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩 } // 并查集的加入集合 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; } int main() { int v, e; int v1, v2, val; vector<Edge> edges; int result_val = 0; cin >> v >> e; while (e--) { cin >> v1 >> v2 >> val; edges.push_back({v1, v2, val}); } // 执行Kruskal算法 // 按边的权值对边进行从小到大排序 sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.val < b.val; }); // 并查集初始化 init(); // 从头开始遍历边 for (Edge edge : edges) { // 并查集，搜出两个节点的祖先 int x = find(edge.l); int y = find(edge.r); // 如果祖先不同，则不在同一个集合 if (x != y) { result_val += edge.val; // 这条边可以作为生成树的边 join(x, y); // 两个节点加入到同一个集合 } } cout << result_val << endl; return 0; }
三、拓扑排序：
作用：
拓扑排序是将，有向图转化为线性关系。
（先上A课，才能上B课，上了A课才能上C课，先上C课才能上B课，上了B课才能上D课）
求上课顺序应该如何排序（有多种排序方式）
最常用的方式是卡恩算法(BFS)（另一种是DFS回溯法）
Kahn算法
两步走：
- 找到入度为0的节点，并加入结果集
- 减去与该节点相连的入度（将该节点从图中移除）
模板
编辑
#include <iostream> #include <vector> #include <queue> #include <unordered_map> using namespace std; int main() { int m, n, s, t; cin >> n >> m; vector<int> inDegree(n, 0); // 记录每个文件的入度 unordered_map<int, vector<int>> umap;// 记录文件依赖关系 vector<int> result; // 记录结果 while (m--) { // s->t，先有s才能有t cin >> s >> t; inDegree[t]++; // t的入度加一 umap[s].push_back(t); // 记录s指向哪些文件 } queue<int> que; for (int i = 0; i < n; i++) { // 入度为0的文件，可以作为开头，先加入队列 if (inDegree[i] == 0) que.push(i); //cout << inDegree[i] << endl; } // int count = 0; while (que.size()) { int cur = que.front(); // 当前选中的文件 que.pop(); //count++; result.push_back(cur); vector<int> files = umap[cur]; //获取该文件指向的文件 if (files.size()) { // cur有后续文件 for (int i = 0; i < files.size(); i++) { inDegree[files[i]] --; // cur的指向的文件入度-1 if(inDegree[files[i]] == 0) que.push(files[i]); } } } if (result.size() == n) { for (int i = 0; i < n - 1; i++) cout << result[i] << " "; cout << result[n - 1]; } else cout << -1 << endl; }
四、最短路径算法
基础定义：
从起点到终点的最短路径。
举一个形象一点的例子：导航地图，你到目的地的推荐路径。
Dijkstra
(迪杰斯特拉算法)--同样是以 “点” 为起始的贪心思想，方法与prim大同小异。
基础应用：
举例：从1到各个节点之间最短距离。（所有权值，必须是正值）
编辑
dijkstra朴素版：
模板：
三部走：
- 选源点到那个节点近，且该节点未被访问过
- 标记该节点为已访问过
- 更新非访问节点，到源点的距离
编辑
#include <iostream> #include <vector> #include <climits> using namespace std; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX)); for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; grid[p1][p2] = val; } int start = 1; int end = n; // 存储从源点到每个节点的最短距离 std::vector<int> minDist(n + 1, INT_MAX); // 记录顶点是否被访问过 std::vector<bool> visited(n + 1, false); minDist[start] = 0; // 起始点到自身的距离为0 for (int i = 1; i <= n; i++) { // 遍历所有节点 int minVal = INT_MAX; int cur = 1; // 1、选距离源点最近且未访问过的节点 for (int v = 1; v <= n; ++v) { if (!visited[v] && minDist[v] < minVal) { minVal = minDist[v]; cur = v; } } visited[cur] = true; // 2、标记该节点已被访问 // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组） for (int v = 1; v <= n; v++) { if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) { minDist[v] = minDist[cur] + grid[cur][v]; } } } if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点 else cout << minDist[end] << endl; // 到达终点最短路径 }
dijkstra堆优化法：
模板：
堆优化法，其实挺好实现的，跟Kruskal挺像，就是以边为中心的贪心思想。
编辑
#include <iostream> #include <vector> #include <list> #include <queue> #include <climits> using namespace std; // 小顶堆 class mycomparison { public: bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { return lhs.second > rhs.second; } }; // 定义一个结构体来表示带权重的边 struct Edge { int to; // 邻接顶点 int val; // 边的权重 Edge(int t, int w): to(t), val(w) {} // 构造函数 }; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<list<Edge>> grid(n + 1); for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 val grid[p1].push_back(Edge(p2, val)); } int start = 1; // 起点 int end = n; // 终点 // 存储从源点到每个节点的最短距离 std::vector<int> minDist(n + 1, INT_MAX); // 记录顶点是否被访问过 std::vector<bool> visited(n + 1, false); // 优先队列中存放 pair<节点，源点到该节点的权值> priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq; // 初始化队列，源点到源点的距离为0，所以初始为0 pq.push(pair<int, int>(start, 0)); minDist[start] = 0; // 起始点到自身的距离为0 while (!pq.empty()) { // 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现） // <节点， 源点到该节点的距离> pair<int, int> cur = pq.top(); pq.pop(); if (visited[cur.first]) continue; // 2. 第二步，该最近节点被标记访问过 visited[cur.first] = true; // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组） for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge // cur指向的节点edge.to，这条边的权值为 edge.val if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist minDist[edge.to] = minDist[cur.first] + edge.val; pq.push(pair<int, int>(edge.to, minDist[edge.to])); } } } if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点 else cout << minDist[end] << endl; // 到达终点最短路径 }
为什么不能有负值：
可以自己模拟一遍
编辑
Bellman ford算法
（贝尔曼-福特算法）- 解决权值为负的问题
核心思想：
贝尔曼-福特算法，的核心是松弛操作。
尝试通过中间节点缩短路径的，就是松弛操作。
如：点之间的最短距离，点A到点B的最短距离是3，点B到点C的最短距离是-2，点A到点C之间的最短距离是2；
点A->点C的最短距离（A先到B，再到C）（3+(-2))=1；减半减半的呢
Bellman_ford
基础应用：
A → B：3（花费为 3） A → C：5（花费为 5） B → C：-1（花费 -1，相当于补贴了钱） B → D：3（花费为 3） C → D：4（花费为 4）
编辑
模板：
编辑
#include <iostream> #include <vector> #include <list> #include <climits> using namespace std; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<vector<int>> grid; // 将所有边保存起来 for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 val grid.push_back({p1, p2, val}); } int start = 1; // 起点 int end = n; // 终点 vector<int> minDist(n + 1 , INT_MAX); minDist[start] = 0; for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次 for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛 int from = side[0]; // 边的出发点 int to = side[1]; // 边的到达点 int price = side[2]; // 边的权值 // 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发 if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price; } } } if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点 else cout << minDist[end] << endl; // 到达终点最短路径 }
Bellman_ford优先队列（SPFA）
其实，SPFA就是对应kruskal算法。以“边”为起始的贪心算法
基础应用：
A → B：3（花费为 3） A → C：5（花费为 5） B → C：-1（花费 -1，相当于补贴了钱） B → D：3（花费为 3） C → D：4（花费为 4）
编辑
模板：
编辑
#include <iostream> #include <vector> #include <queue> #include <list> #include <climits> using namespace std; struct Edge { //邻接表 int to; // 链接的节点 int val; // 边的权重 Edge(int t, int w): to(t), val(w) {} // 构造函数 }; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<list<Edge>> grid(n + 1); vector<bool> isInQueue(n + 1); // 加入优化，已经在队里里的元素不用重复添加 // 将所有边保存起来 for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 val grid[p1].push_back(Edge(p2, val)); } int start = 1; // 起点 int end = n; // 终点 vector<int> minDist(n + 1 , INT_MAX); minDist[start] = 0; queue<int> que; que.push(start); while (!que.empty()) { int node = que.front(); que.pop(); isInQueue[node] = false; // 从队列里取出的时候，要取消标记，我们只保证已经在队列里的元素不用重复加入 for (Edge edge : grid[node]) { int from = node; int to = edge.to; int value = edge.val; if (minDist[to] > minDist[from] + value) { // 开始松弛 minDist[to] = minDist[from] + value; if (isInQueue[to] == false) { // 已经在队列里的元素不用重复添加 que.push(to); isInQueue[to] = true; } } } } if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点 else cout << minDist[end] << endl; // 到达终点最短路径 }
Bellman_ford判断负权回路
基础应用：
图中，存在回路，并且回路的值为负值
模板：
1、朴素版
朴素版，其实是最好理解的！
没有负权回路时会循环n-1次，之后n、n+1、n+2...结果都不会在变。
若出现负权回路！不论循环多少次，内容一直会改变。
#include <iostream> #include <vector> #include <list> #include <climits> using namespace std; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<vector<int>> grid; for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 val grid.push_back({p1, p2, val}); } int start = 1; // 起点 int end = n; // 终点 vector<int> minDist(n + 1 , INT_MAX); minDist[start] = 0; bool flag = false; for (int i = 1; i <= n; i++) { // 这里我们松弛n次，最后一次判断负权回路 for (vector<int> &side : grid) { int from = side[0]; int to = side[1]; int price = side[2]; if (i < n) { if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price; } else { // 多加一次松弛判断负权回路 if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) flag = true; } } } if (flag) cout << "circle" << endl; else if (minDist[end] == INT_MAX) { cout << "unconnected" << endl; } else { cout << minDist[end] << endl; } }
2、SPFA
若要用优先队列解决的话，可以根据他的一个性质，每个节点最多被松弛n-1次。
（也就是做n-1次，中间节点）
一点超过n-1次，就会说明出现了负权回路。
#include <iostream> #include <vector> #include <queue> #include <list> #include <climits> using namespace std; struct Edge { //邻接表 int to; // 链接的节点 int val; // 边的权重 Edge(int t, int w): to(t), val(w) {} // 构造函数 }; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<list<Edge>> grid(n + 1); // 邻接表 // 将所有边保存起来 for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 val grid[p1].push_back(Edge(p2, val)); } int start = 1; // 起点 int end = n; // 终点 vector<int> minDist(n + 1 , INT_MAX); minDist[start] = 0; queue<int> que; que.push(start); // 队列里放入起点 vector<int> count(n+1, 0); // 记录节点加入队列几次 count[start]++; bool flag = false; while (!que.empty()) { int node = que.front(); que.pop(); for (Edge edge : grid[node]) { int from = node; int to = edge.to; int value = edge.val; if (minDist[to] > minDist[from] + value) { // 开始松弛 minDist[to] = minDist[from] + value; que.push(to); count[to]++; if (count[to] == n) {// 如果加入队列次数超过 n-1次 就说明该图与负权回路 flag = true; while (!que.empty()) que.pop(); break; } } } } if (flag) cout << "circle" << endl; else if (minDist[end] == INT_MAX) { cout << "unconnected" << endl; } else { cout << minDist[end] << endl; } }
Bellman_ford之单源最短路
基础应用：
共有1~n各城市，要求城市1->城市n，最多经历k个城市。
模板：
其实挺容易理解的，只要创建两个minDist，复用上一个minDist就行。
在这个前提下，只需要k次，就能求出所有（1~k）的城市。
1、朴素版：
// 版本二 #include <iostream> #include <vector> #include <list> #include <climits> using namespace std; int main() { int src, dst,k ,p1, p2, val ,m , n; cin >> n >> m; vector<vector<int>> grid; for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; grid.push_back({p1, p2, val}); } cin >> src >> dst >> k; vector<int> minDist(n + 1 , INT_MAX); minDist[src] = 0; vector<int> minDist_copy(n + 1); // 用来记录上一次遍历的结果 for (int i = 1; i <= k + 1; i++) { minDist_copy = minDist; // 获取上一次计算的结果 for (vector<int> &side : grid) { int from = side[0]; int to = side[1]; int price = side[2]; // 注意使用 minDist_copy 来计算 minDist if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) { minDist[to] = minDist_copy[from] + price; } } } if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点 else cout << minDist[dst] << endl; // 到达终点最短路径 }
2、SPFA：
// 将所有边保存起来 for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; // p1 指向 p2，权值为 val grid[p1].push_back(Edge(p2, val)); } int start, end, k; cin >> start >> end >> k; k++; vector<int> minDist(n + 1 , INT_MAX); vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果 minDist[start] = 0; queue<int> que; que.push(start); // 队列里放入起点 int que_size; while (k-- && !que.empty()) { minDist_copy = minDist; // 获取上一次计算的结果 que_size = que.size(); // 记录上次入队列的节点个数 while (que_size--) { // 上一轮松弛入队列的节点，这次对应的边都要做松弛 int node = que.front(); que.pop(); for (Edge edge : grid[node]) { int from = node; int to = edge.to; int price = edge.val; if (minDist[to] > minDist_copy[from] + price) { minDist[to] = minDist_copy[from] + price; que.push(to); } } } } if (minDist[end] == INT_MAX) cout << "unreachable" << endl; else cout << minDist[end] << endl; }
Floyed算法
基础应用：
假设你有一张包含多个城市的交通图，想一次性知道 任意两个城市之间的最短路线（比如全国城市间的多对多导航）。Floyd 算法专门解决这类 全源最短路径 问题，即求出图中所有点对之间的最短路径。
核心思想:
尝试让每个节点做为一个 “中转节点” 。看能不能缩短两点之间的距离。
适合求多元最短路径，n<200最佳（O(n^3)）
模板：
编辑
#include <iostream> #include <vector> using namespace std; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005)); // 因为边的最大距离是10^4 for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; grid[p1][p2] = val; grid[p2][p1] = val; // 注意这里是双向图 } // 开始 floyd for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]); } } } // 输出结果 int z, start, end; cin >> z; while (z--) { cin >> start >> end; if (grid[start][end] == 10005) cout << -1 << endl; else cout << grid[start][end] << endl; } }
A*算法
Astar的核心，在于 启发式函数。
他是建立在BFS广搜的基础之上。
用以下这道题目举例子：
编辑
模板：
#include <iostream> #include <queue> #include <cstring> using namespace std; // 本题有好几个地方需要注意 // 第一，创建结构体，并与优先队列相结合 // 第二，创建二维数组用于去重，并记录走了多少步 // 第三，启发式搜索的权值，用欧拉函数计算，且欧拉函数 //（起点到该点经过的距离）+（该点的距离到终点的距离） // 其中从起点到该点的距离，容易被用错。是依次经过的距离，不是直线距离。 int a1,a2,b1,b2; struct knight{ int m1,m2; int g,h,f; bool operator<(const knight& k)const{ // 调节为小根堆 return f>k.f; } }; int visited[1005][1005]; int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2}; int get_squeeze(int m1,int m2,int b1,int b2){ return (b1-m1)*(b1-m1)+(b2-m2)*(b2-m2); } void astar(knight k){ priority_queue<knight> pq; pq.push(k); knight node,cur; while(!pq.empty()){ node = pq.top(); pq.pop(); if(node.m1==b1&&node.m2==b2){ cout<<visited[node.m1][node.m2]<<endl; break; } for(int i=0; i<8; ++i){ cur = node; cur.m1+=dir[i][0]; cur.m2+=dir[i][1]; if(cur.m1<1||cur.m1>1000||cur.m2<1||cur.m2>1000) continue; if(visited[cur.m1][cur.m2]) continue; visited[cur.m1][cur.m2]=visited[node.m1][node.m2]+1; // 需要在原来的基础上进行操作 cur.g=node.g+5; // 1*1+2*2=5 cur.h=get_squeeze(cur.m1,cur.m2,b1,b2); cur.f=cur.h+cur.g; pq.push(cur); } } } int main(){ int t; cin>>t; while(t--){ cin>>a1>>a2>>b1>>b2; if(a1==b1&&a2==b2){ // 直接排除意外情况 cout<<0<<endl; continue; } memset(visited,0,sizeof visited); knight k; k.m1 = a1; k.m2 = a2; k.g = 0; k.h = get_squeeze(k.m1,k.m2,b1,b2); astar(k); } return 0; }
借鉴博客：
1、图论总结篇
