4 - 单源最短路
快速入门图论！本文介绍图的”单源最短路“问题，并介绍解决这类问题的Dijkstra算法，BellmanFord算法和SPFA算法。
单源最短路问题
就是求图中 一个点到其他所有点的最短距离。这个问题还能分为两类：
所有边权都是正数：可以用朴素版（适用于稠密图，复杂度
）/堆优化版（适用于稀疏图，复杂度 ）的Dijkstra算法解决。 稠密图：点少边多
稀疏图：点多边少
存在负的权边：可以用 Bellman-Ford算法（复杂度
）或 SPFA算法（复杂度 ）来解决。
不带负权边
Dijkstra算法
朴素版（稠密图）
思路
维护三个数组：
g[i][j]表示节点i到节点j的边权，如果两点不连通，定义g[i][j] = 正无穷。需要注意的是，建图过程中可能会出现重边，因此g[i][j]要确保是最小的边。dist[i]表示起点k到节点i的最短路长度。一开始dist[k] = 0，其余dist[i] = 正无穷。visited数组，表示所有节点的访问情况，即该点是否被加入到集合S中。
算法目标是算出最终的dist数组，这样就知道起点k到其他所有点的最短距离了。
朴素版算法思路如下，可以发现和求最小生成树的Prim算法思路比较像：
// 1.初始化操作(假设1是起点)
dist[1] = 0, dist[i] = INF;
// 2.求dist[]
for i = 0 ~ n
t <- 不在集合S中距离最近的点
集合S <- t
用t更新起点到其他点的距离, 取最小代码实现
// 朴素版Dij(节点为1起点)
vector<int> dist(n + 5, maxVal), visited(n + 5, 0);
// 1.初始化操作
dist[k] = 0;
// 2.求dist
for (int i = 0; i < n; ++i)
{
// t <- 不在集合S中距离最近的点
int t = -1;
for (int j = 1; j <= n; ++j)
if (!visited[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 集合S <- t
visited[t] = 1;
// 用t更新距离
for (int j = 1; j <= n; ++j)
{
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}堆优化（稀疏图）
思路
对于稀疏图（边很少）来说，应该用邻接表来存储边，边的描述如下：
struct Edge {
int to; // 链接的节点
int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
vector<list<Edge>> grid(n + 1); // 邻接表代码实现
对于取最小值边的操作，可以通过优先队列简化实现，代码如下：
vector<int> dist(n + 1, intMAX);
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[k] = 0;
heap.push({dist[k], k});
while (!heap.empty())
{
// 这里不能用&, 因为heap.top()是临时对象, 用了引用有问题
auto [curDist, cur] = heap.top();
heap.pop();
if (curDist > dist[cur])
continue;
for (const auto& edge : graph[cur])
{
int newDist = curDist + edge.val;
if (newDist < dist[edge.to])
{
dist[edge.to] = newDist;
heap.push({dist[edge.to], edge.to});
}
}
}
带负权边
Bellman-Ford算法
Bellman-Ford算法是一种处理存在负权边的单源最短路问题的算法。核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。因此要获得从起点到终点的最短距离，就要对所有边松弛n-1次（所有节点与起点连接的边数最多也就是 n-1 条边）。
思路
该算法需要维护：
dist数组，维护起点k到其他点的距离。初始化时，dist[k] = 0，其他都是正无穷。
代码实现
// Bellman-Ford 求负权边的单源最短路
vector<int> dist(n + 1, IntMax);
// 1. 初始化
dist[1] = 0;
// 2. 对所有边进行n-1次松弛操作
for (int i = 1; i < n; ++i)
{
for (auto& edge : edges)
{
// 防止对未经过的点进行松弛操作
if (dist[edge.from] != IntMax)
{
// 松弛操作:
// min(从原点到to的距离, 从原点经过from再到to的距离);
dist[edge.to] = min(dist[edge.to], dist[edge.from] + edge.val);
}
}
}判断负环
对所有边进行n - 1次松弛操作后便能求出最短路，如果第n次，第n + 1次等遍历还能进行松弛操作，说明图中有负环。
代码如下：
// Bellman-Ford
vector<int> dist(n + 1, IntMax);
bool hasCircle = false;
dist[1] = 0;
// 刻意对所有边进行n次松弛操作, 如果
// 第n次还能松弛, 说明图中有负环
for (int i = 0; i <= n; ++i)
{
for (const auto& edge : edges)
{
if (dist[edge.from] != IntMax &&
dist[edge.to] > dist[edge.from] + edge.val)
{
if (i >= n)
{
hasCircle = true;
}
else
{
dist[edge.to] = dist[edge.from] + edge.val;
}
}
}
}
if (hasCircle)
cout << "circle";
else if (dist[n] == IntMax)
cout << "unconnected";
else
cout << dist[n];有限最短路问题
有时候题目会要求只能走X个边，求该前提下的最短路。这代表经过两条边权为2；经过一条边权为3；如果最短路限制一条边，那么答案只能是3。
代码如下，和原来相比多了一个backup数组，不使用dist数组更新的原因是，dist数组内的数据经过更短路的边数可能超过了题给限制，使用backup是最稳妥的。
// Bellman-Ford
vector<int> dist(n + 1, IntMax);
vector<int> distCp;
// 1. 初始化
dist[src] = 0;
// 2. 进行松弛操作
// 这里K是经过的节点数, 那么经过的边数
// 就是K + 1, 所以要循环K + 1次
for (int i = 1; i <= k + 1; ++i)
{
distCp = dist;
for (const auto& edge : edges)
{
if (dist[edge.from] != IntMax &&
dist[edge.to] > distCp[edge.from] + edge.val)
{
dist[edge.to] = distCp[edge.from] + edge.val;
}
}
}
if (dist[dst] != IntMax)
cout << dist[dst];
else
cout << "unreachable";SPFA算法
SPFA算法是Bellman Ford算法的队列优化版，用于求没有负环的图的单源最短路，因此也能用它来判断图中是否有负环。
SPFA的优化思路是，没有必要对所有边进行松弛操作，只对计算过的节点相关的节点进行松弛操作，可以用BFS来做优化。该算法需要维护如下数据结构：
- dist数组：和之前的意义相同；
- visited数组：用于BFS，标识已入队的元素；
思路
该算法需要维护：
dist数组visited数组，防止队列中存入重复的点
算法思路如下：
//1. 初始化 (n个节点, m条边)
dist[0 ~ n] = 正无穷;
dist[k] = 0;
queue <- 1;
visited[k] = 1;
//2. BFS
while queue不空
t <- q.front();
q.pop();
visited[t] = 0;
for t的所有出边t->b, 其中权为w
看情况更新dist[j];
如果b不在队列中
visited[b] = 1;
queue <- b;代码实现
// SPFA 求负权边的单源最短路
vector<int> dist(n + 1, IntMax);
vector<bool> visited(n + 1, false);
queue<int> q;
// 1. 初始化
dist[1] = 0;
visited[1] = true;
q.push(1);
// 2. BFS优化, 不松弛无效边
while (!q.empty())
{
int cur = q.front();
q.pop();
visited[cur] = false;
for (auto& edge : edges)
{
// 松弛操作
if (dist[edge.from] != IntMax &&
dist[edge.to] > dist[edge.from] + edge.val)
{
dist[edge.to] = dist[edge.from] + edge.val;
// 将未入队的节点入队
if (!visited[edge.to])
{
q.push(edge.to);
visited[edge.to] = true;
}
}
}
}
if (dist[n] == IntMax)
cout << "unconnected";
else
cout << dist[n];判断负环
在极端情况下（图中的每个节点都相连），每个节点的入度为n - 1，因此每个节点最多加入n - 1次队列。如果在计算过程中有节点的入队次数超过n - 1，说明图中有负环。
为什么不需要 visited 数组?
在 标准 SPFA 中，visited 数组的作用是 避免重复入队（即防止同一个节点多次进入队列）。但在 负环检测 时，visited 数组反而会导致 漏判负环，原因如下：
- 负环会导致节点被无限次松弛：如果存在负环，某些节点会被反复加入队列（因为
dist会不断被更新得更小）。 visited数组会阻止节点多次入队：如果使用visited，某些节点可能无法被多次处理，导致算法无法正确检测到负环（因为负环的检测依赖于节点的重复入队次数）。
代码如下：
// SPFA
vector<int> dist(n + 1, IntMax);
queue<int> q;
vector<int> count(n + 1);
bool hasCircle = false;
// 1. 初始化
dist[1] = 0;
q.push(1);
++count[1];
// 2. BFS
while (!q.empty() && !hasCircle)
{
int cur = q.front();
q.pop();
for (const auto& edge : edges)
{
if (dist[edge.from] != IntMax &&
dist[edge.to] > dist[edge.from] + edge.val)
{
dist[edge.to] = dist[edge.from] + edge.val;
{
q.push(edge.to);
++count[edge.to];
if (count[edge.to] >= n)
{
hasCircle = true;
break;
}
}
}
}
}
if (hasCircle)
cout << "circle";
else if (dist[n] == IntMax)
cout << "unconnected";
else
cout << dist[n];有限最短路问题
题单
不带负权边
743. 网络延迟时间 - 力扣（LeetCode）
使用Dijkstra算法求出点k到其他所有点的最短距，然后最长的距离就是答案。如果最长的距离仍然是INF，那么说明图不是联通的，无解返回-1。
朴素Dijkstra
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
// 建图
int maxVal = numeric_limits<int>::max() / 2;
vector<vector<int>> g(n + 5, vector<int>(n + 5, maxVal));
for (auto& edge : times)
{
int a = edge[0], b = edge[1], v = edge[2];
// 防止重边, 每次记录最小值
g[a][b] = min(g[a][b], v);
}
// 朴素版Dij
vector<int> dist(n + 5, maxVal), visited(n + 5, 0);
// 1.初始化操作
dist[k] = 0;
// 2.求dist
for (int i = 0; i < n; ++i)
{
// t <- 不在集合S中距离最近的点
int t = -1;
for (int j = 1; j <= n; ++j)
if (!visited[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 集合S <- t
visited[t] = 1;
// 用t更新距离
for (int j = 1; j <= n; ++j)
{
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
int ans = *max_element(dist.begin() + 1, dist.begin() + n + 1);
return ans == maxVal ? -1 : ans;
}堆优化Dijkstra
struct Graph
{
vector<int> h, val, e, ne;
int idx;
void add(int a, int b, int v)
{
val[idx] = v;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
Graph(int n, int m)
: h(n + 5, -1),
val(m + 5), e(m + 5), ne(m + 5), idx(0) {}
};
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
// 先建图
int maxVal = numeric_limits<int>::max() / 2;
Graph g(n, times.size());
for (auto& edge : times)
{
// 使用邻接表的图不怕重边
g.add(edge[0], edge[1], edge[2]);
}
// 堆优化版Dijkstra
vector<int> dist(n + 5, maxVal), visited(n + 5, 0);
// 存储: {距离, 节点编号}
using PII = pair<int, int>;
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 1.初始化操作
dist[k] = 0;
heap.push({dist[k], k});
// 2. 求dist
while (!heap.empty())
{
// 加速寻找t
auto [curDist, cur] = heap.top();
heap.pop();
// 集合S <- t
if (visited[cur])
continue;
else
visited[cur] = 1;
// 用t更新其他点的距离
for (int idx = g.h[cur]; idx != -1; idx = g.ne[idx])
{
int j = g.e[idx], v = g.val[idx];
if (dist[j] > dist[cur] + v)
{
dist[j] = dist[cur] + v;
heap.push({dist[j], j});
}
}
}
int ans = *max_element(dist.begin() + 1, dist.begin() + n + 1);
return ans == maxVal ? -1 : ans;
}还没做的题
2642. 设计可以求最短路径的图类 1811
1514. 概率最大的路径 1846
1631. 最小体力消耗路径 1948 做法不止一种
1368. 使网格图至少有一条有效路径的最小代价 2069 也可以 0-1 BFS
1786. 从第一个节点出发到最后一个节点的受限路径数 2079
1976. 到达目的地的方案数 2095
2662. 前往目标的最小代价 2154
2045. 到达目的地的第二短时间 2202 也可以 BFS
882. 细分图中的可到达节点 2328
2203. 得到要求路径的最小带权子图 2364
2577. 在网格图中访问一个格子的最少时间 2382
2699. 修改图中的边权 2874
2093. 前往目标城市的最小费用（会员题）
2473. 购买苹果的最低成本（会员题）
2714. 找到最短路径的 K 次跨越（会员题）
2737. 找到最近的标记节点（会员题）
LCP 35. 电动车游城市
LCP 56. 信物传送 也可以 0-1 BFS带负权边
853. 有边数限制的最短路 - AcWing题库
边权为负数，不能用Dijkstra算法。可能存在负权回路，即可能存在负环，不能用SPFA算法。因此只能用Bellman-Ford算法。
这道题特殊的地方在于，要求的最短路有边数限制，这代表经过两条边权为2；经过一条边权为3；如果最短路限制一条边，那么答案只能是3。
参考代码如下:
int maxVal = numeric_limits<int>::max() / 2;
struct Edge
{
int a, b, w;
Edge(int a, int b, int w) : a(a), b(b), w(w) {}
};
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<Edge> edges;
for (int i = 0; i < m; ++i)
{
int a, b, w;
cin >> a >> b >> w;
edges.emplace_back(a, b, w);
}
//Bellman-Ford
vector<int> dist(n + 5, maxVal);
vector<int> backup;
// 1. 初始化
dist[1] = 0;
// 2. 松弛操作
for (int i = 0; i < k; ++i)
{
backup = dist;
for (int j = 0; j < m; ++j)
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
}
}
int ans = *max_element(dist.begin() + 1, dist.begin() + 1 + n);
if (dist[n] >= maxVal / 2)
cout << "impossible\n";
else
cout << dist[n];
}需要注意的是：
- 这里使用
backup数组而不使用dist数组更新的原因是，dist数组内的数据经过更短路的边数可能超过了题给限制，使用backup是最稳妥的。 - 这里判断答案是否正确不是
dist[n] == maxVal了，因为图中有负环，可能会让dist[n] < maxVal。因此需要改成dist[n] >= maxVal / 2。
851. spfa求最短路 - AcWing题库
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
using namespace std;
struct Graph
{
vector<int> h, val, e, ne;
int idx;
void add(int a, int b, int w)
{
val[idx] = w;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
Graph(int n, int m) : h(n + 5, -1), val(m + 5), e(m + 5), ne(m + 5), idx(0) {}
};
int main()
{
int n, m;
cin >> n >> m;
Graph g(n, m);
for (int i = 0; i < m; ++i)
{
int a, b, w;
cin >> a >> b >> w;
g.add(a, b, w);
}
// SPFA
int maxVal = numeric_limits<int>::max() / 2;
vector<int> dist(n + 5, maxVal), visited(n + 5, 0);
queue<int> q;
// 1. 初始化
dist[1] = 0;
visited[1] = 1;
q.push(1);
// 2. BFS
while (!q.empty())
{
int t = q.front();
q.pop();
visited[t] = 0;
for (int idx = g.h[t]; idx != -1; idx = g.ne[idx])
{
int j = g.e[idx], w = g.val[idx];
if (dist[j] > dist[t] + w)
{
dist[j] = dist[t] + w;
if (!visited[j])
{
visited[j] = 1;
q.push(j);
}
}
}
}
if (dist[n] >= maxVal / 2)
cout << "impossible";
else
cout << dist[n];
return 0;
}