1. 单源最短路
单一边权 BFS
原理：由于边权为单一值，可使用广度优先搜索（BFS）来求解最短路。BFS 会逐层扩展节点，由于边权相同，第一次到达某个节点时的路径长度就是最短路径长度。
用法：适用于边权都为 1 的图，可快速求出从源点到其他所有节点的最短路径。
代码：
#include <iostream>#include <queue>#include <vector>using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];int dist[MAXN];
void bfs(int s) {
queue<int> q;
fill(dist, dist + MAXN, -1);
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;
}
0 - 1 边权双端队列 BFS
原理：使用双端队列来优化 BFS 过程。对于边权为 0 的边，将其终点插入队头；对于边权为 1 的边，将其终点插入队尾。这样能保证队列中元素的距离是单调递增的。
用法：适用于图中边权只有 0 和 1 的情况。
代码：
#include <iostream>#include <deque>#include <vector>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];
void bfs_01(int s) {
deque<int> q;
fill(dist, dist + MAXN, -1);
dist[s] = 0;
q.push_back(s);
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto [v, w] : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + w;
if (w == 0) {
q.push_front(v);
} else {
q.push_back(v);
}
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
bfs_01(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;
}
朴素迪杰斯特拉
原理：通过贪心策略，每次从未确定最短路径的节点中选择距离源点最近的节点，然后以该节点为中间点更新其他节点的距离。
用法：适用于边权非负且节点数较少的图，时间复杂度为 O(V2)稠密图。
代码：
#include <iostream>#include <vector>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];int dist[MAXN];bool vis[MAXN];
void dijkstra(int s, int n) {
fill(dist, dist + MAXN, INT_MAX);
fill(vis, vis + MAXN, false);
dist[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = true;
for (int v = 1; v <= n; v++) {
if (!vis[v] && graph[u][v] != INT_MAX) {
dist[v] = min(dist[v], dist[u] + graph[u][v]);
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
}
dijkstra(s, n);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;}
堆优化迪杰斯特拉
原理：使用优先队列（小根堆）来优化每次选择距离源点最近的节点的过程，减少时间复杂度。
用法：适用于边权非负且节点数较多的稀疏图，时间复杂度为 O((V+E)logV)。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(dist, dist + MAXN, INT_MAX);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;}
Bellman - Ford
原理：通过对所有边进行 V−1 次松弛操作，来更新节点的最短距离。如果图中存在负环，经过 V−1 次松弛操作后，仍然可以继续松弛。
用法：适用于存在负权边的图，也可用于求解只经过 k 条边的最短路。
代码：
#include <iostream>#include <vector>#include <climits>using namespace std;
const int MAXN = 100005;struct Edge {
int u, v, w;};
vector<Edge> edges;int dist[MAXN];
bool bellman_ford(int s, int n) {
fill(dist, dist + MAXN, INT_MAX);
dist[s] = 0;
int flag=0;
for (int i = 0; i < n ; i++) {
for (auto [u, v, w] : edges) {
flag=0;
if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
flag=1;
if(i==n)return true;//如果链接了n条边还能松弛就说明有负环
}
}
}
return false;
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
if (bellman_ford(s, n)) {
cout << "存在负环" << endl;
} else {
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
return 0;
}
SPFA
原理：SPFA 是 Bellman - Ford 算法的优化版本，使用队列来维护需要松弛的节点。
用法：适用于存在负权边的图，但在某些特殊图中可能会退化为 O(VE)。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];int cnt[MAXN]; // 记录每个节点入队的次数bool in_queue[MAXN];
bool spfa(int s, int n) {
fill(dist, dist + MAXN, INT_MAX);
fill(cnt, cnt + MAXN, 0);
fill(in_queue, in_queue + MAXN, false);
dist[s] = 0;
queue<int> q;
q.push(s);
in_queue[s] = true;
cnt[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!in_queue[v]) {
q.push(v);
in_queue[v] = true;
cnt[v]++;
if (cnt[v] > n) {
return true; // 存在负环
}
}
}
}
}
return false;}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
if (spfa(s, n)) {
cout << "存在负环" << endl;
} else {
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
return 0;}
2. 单源最短路和其他算法的结合
二分答案 + 双端队列求最短路
以 “可以免费建立 k 条边，求最小的花费” 为例，二分答案 mid，将边权大于 mid 的边视为 1，边权小于等于 mid 的边视为 0，使用双端队列 BFS 求解最短路，判断最短路径上大于 mid 的边数是否小于等于 k。
缩点 + 最短路
先使用 Tarjan 算法求出图的强连通分量，然后进行缩点，将每个强连通分量缩成一个点，再在缩点后的图上进行最短路计算。
首位两次最短路求节点之间的最大差值（以 2009 年提高组最优贸易问题为例）
分别从起点和终点进行最短路计算，记录从起点到每个节点的最小价格和从终点到每个节点的最大价格，然后枚举每个节点，计算最大差值。
3. 单源最短路自身的拓展
多起点多终点用虚拟节点
添加一个虚拟起点和一个虚拟终点，将虚拟起点与所有起点相连，边权为 0，将所有终点与虚拟终点相连，边权为 0，然后求解从虚拟起点到虚拟终点的最短路。
分图层的最短路
以 “拯救大兵瑞恩” 为例，使用三维数组 d[x][y][st] 记录状态，其中 (x,y) 表示节点坐标，st 表示当前拥有的钥匙状态，只有拿到了钥匙才能进入到对应层的一些状态，在 BFS 或 Dijkstra 过程中更新状态。
新的一个例题：
题目背景
本题原题数据极弱，Subtask 0 中的测试点为原题测试点，Subtask 1 中的测试点为 Hack 数据。
题目描述
C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1∼n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 1∼n 号城市的水晶球价格分别为 4,3,5,6,1。
阿龙可以选择如下一条线路：1→2→3→5，并在 2 号城市以 3 的价格买入水晶球，在 3 号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。
阿龙也可以选择如下一条线路：1→4→5→4→5，并在第 1 次到达 5 号城市时以 1 的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数 x,y,z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。
输出格式
一个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 0。
代码：
分层图，第一层原本的图，第二层，第一层购买后到达的图，第三层，第二层对应节点卖出的图
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=100010;
unordered_map<int,vector<pii>>e;
int n,m;
int a[N];
int dis[N*3];
bool vis[N*3];
void spfa(int s){
memset(dis,-0x3f,sizeof dis);
queue<int> q;
q.push(s);
dis[s]=0;
vis[s]=1;
while(q.size()){
int u=q.front();
q.pop();
vis[u]=0;
for(auto t:e[u]){
int v=t.first,w=t.second;
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
e[i].push_back({i+n,-a[i]});
e[n+i].push_back({i+2*n,a[i]});
}
for(int i=0;i<m;i++){
int u,v,op;
scanf("%d%d%d",&u,&v,&op);
if(op==2){
e[u].push_back({v,0});
e[u+n].push_back({v+n,0});
e[u+2*n].push_back({v+2*n,0});
e[v].push_back({u,0});
e[v+n].push_back({u+n,0});
e[v+2*n].push_back({u+2*n,0});
}else{
e[u].push_back({v,0});
e[u+n].push_back({v+n,0});
e[u+2*n].push_back({v+2*n,0});
}
}
spfa(1);
cout<<dis[3*n];
}
最短路计数
在更新最短路径时，记录路径数量。如果经过某个点的路径更短，计数为 1；如果相等，计数累加。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;const int MOD = 1e9 + 7;
vector<pair<int, int>> adj[MAXN];int dist[MAXN];int cnt[MAXN];
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(dist, dist + MAXN, INT_MAX);
fill(cnt, cnt + MAXN, 0);
dist[s] = 0;
cnt[s] = 1;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
cnt[v] = cnt[u];
pq.push({dist[v], v});
} else if (dist[v] == dist[u] + w) {
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " " << cnt[i] << endl;
}
return 0;}
最短路和次短路
使用两个数组分别记录最短路和次短路，在更新时同时更新这两个数组。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN];int dist1[MAXN]; // 最短路int dist2[MAXN]; // 次短路
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(dist1, dist1 + MAXN, INT_MAX);
fill(dist2, dist2 + MAXN, INT_MAX);
dist1[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist2[u]) continue;
for (auto [v, w] : adj[u]) {
int new_dist = d + w;
if (new_dist < dist1[v]) {
dist2[v] = dist1[v];
dist1[v] = new_dist;
pq.push({dist1[v], v});
} else if (new_dist < dist2[v] && new_dist > dist1[v]) {
dist2[v] = new_dist;
pq.push({dist2[v], v});
}
}
}}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist1[i] << " " << dist2[i] << endl;
}
return 0;}
4. 全源最短路
Floyd 算法
原理：通过动态规划的思想，枚举中间节点 k，更新任意两点之间的最短距离。
用法：适用于求解任意两点之间的最短路径，也可用于处理联通问题、传递闭包和最小环问题。
代码：
#include <iostream>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];
void floyd(int 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] != INT_MAX && graph[k][j] != INT_MAX) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
}
floyd(n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
return 0;}
最小环
在 Floyd 算法的基础上，记录最小环的长度。
cpp
#include <iostream>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];int dist[MAXN][MAXN];
int floyd_min_cycle(int n) {
int ans = INT_MAX;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++) {
for (int j = i + 1; j < k; j++) {
if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX && dist[i][j] != INT_MAX) {
ans = min(ans, graph[i][k] + graph[k][j] + dist[i][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
graph[v][u] = min(graph[v][u], w);
}
int min_cycle = floyd_min_cycle(n);
if (min_cycle == INT_MAX) {
cout << "不存在最小环" << endl;
} else {
cout << "最小环长度为: " << min_cycle << endl;
}
return 0;
}
5. 最小生成树
Prim 算法
原理：从一个节点开始，每次选择与当前生成树相连的边中权值最小的边，将其加入生成树，直到所有节点都被加入。
用法：适用于稠密图，时间复杂度为 O(V2)。
代码：
#include <iostream>#include <vector>#include <climits>using namespace std;
const int MAXN = 1005;int graph[MAXN][MAXN];bool vis[MAXN];int dist[MAXN];
int prim(int n) {
fill(vis, vis + MAXN, false);
fill(dist, dist + MAXN, INT_MAX);
dist[1] = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = true;
ans += dist[u];
for (int v = 1; v <= n; v++) {
if (!vis[v] && graph[u][v] != INT_MAX) {
dist[v] = min(dist[v], graph[u][v]);
}
}
}
return ans;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INT_MAX;
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = min(graph[u][v], w);
graph[v][u] = min(graph[v][u], w);
}
int mst = prim(n);
cout << "最小生成树的权值为: " << mst << endl;
return 0;}
Kruskal 算法
原理：将所有边按权值从小到大排序，然后依次选择边，如果该边的两个端点不在同一个连通分量中，则将该边加入生成树，直到所有节点都在同一个连通分量中。
用法：适用于稀疏图，时间复杂度为 O(ElogE)。
代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;
const int MAXN = 100005;struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}};
vector<Edge> edges;int parent[MAXN];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];}
void unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
}}
int kruskal(int n) {
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int ans = 0;
int cnt = 0;
for (auto [u, v, w] : edges) {
if (find(u) != find(v)) {
unite(u, v);
ans += w;
cnt++;
if (cnt == n - 1) {
break;
}
}
}
return ans;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
int mst = kruskal(n);
cout << "最小生成树的权值为: " << mst << endl;
return 0;}
6. 最小生成树的运用
引入虚拟节点
以 “有 k 个点可以用卫星链接，求出让全部点联通的最小花费” 为例，添加一个虚拟节点，将该节点与可以用卫星链接的 k 个点相连，边权为 0，然后使用 Kruskal 或 Prim 算法求解最小生成树。
允许 k 个联通块的最小花费
使用 Kruskal 算法，在合并节点的过程中，当合并到 k 个联通块时停止，此时的花费即为最小花费。
代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;
const int MAXN = 100005;struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}};
vector<Edge> edges;int parent[MAXN];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];}
void unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
}}
int kruskal(int n, int k) {
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int ans = 0;
int cnt = n;
for (auto [u, v, w] : edges) {
if (find(u) != find(v)) {
unite(u, v);
ans += w;
cnt--;
if (cnt == k) {
break;
}
}
}
return ans;}
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
int cost = kruskal(n, k);
cout << "允许 " << k << " 个联通块的最小花费为: " << cost << endl;
return 0;
}
——红黑树及模拟实现)
