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]);
}
}堆优化（稀疏图）
思路
在寻找t的过程中可以用小根堆加速寻找，此外，这里使用邻接表存储图。
代码实现
// 堆优化版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});
}
}
}Bellman-Ford算法
Bellman-Ford算法是一种处理存在负权边的单元最短路问题的算法。 其实现方式是通过m次迭代求出从源点到终点不超过m条边构成的最短路的路径。
思路
该算法需要维护：
- 图的实现，可以是边集数组、邻接表、邻接矩阵等。
dist数组，维护起点k到其他点的距离。初始化时，dist[k] = 0，其他都是正无穷。
该算法的思路如下：
//1. 初始化 (n个节点, m条边)
dist[0 ~ n] = 正无穷;
dist[k] = 0;
//2. 迭代求从起点到终点不超过m条边构成的最短路路径
for i = 0 ~ 边数m
for 所有权为w的边a->b
// 松弛操作
dist[b] = min(dist[b], dist[a] + w);代码实现
//Bellman-Ford
vector<int> dist(n + 5, maxVal);
vector<int> backup;
// 1. 初始化
dist[1] = 0;
// 2. 松弛操作
for (int i = 0; i < m; ++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], dist[a] + w);
}
}SPFA算法
只要图中没有负环就能用SPFA，一般的最短路问题里都没有负环。SPFA算法其实是对Bellman-Ford算法的一个优化，在更新dist[b]的过程中，只有dist[a]变小了，dist[b]才有可能变小，因此能用BFS做优化。
PS：SPFA也能用来判断负环。
思路
该算法需要维护：
- 存储图的邻接表
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
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);
}
}
}
}题单
不带负权边
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;
}