一. 单源最短路：Dijkstra 算法
1.套路
1.Dijkstra 算法介绍
(1)定义 g[i][j] 表示节点 i 到节点 j 这条边的边权。如果没有 i 到 j 的边，则 g[i][j]=∞。
(2)定义 dis[i] 表示起点 k 到节点 i 的最短路长度，一开始 dis[k]=0，其余 dis[i]=∞ 表示尚未计算出。
(3)我们的目标是计算出最终的 dis 数组。
- 首先更新起点 k 到其邻居 y 的最短路，即更新
dis[y]为g[k][y]。 - 然后取除了起点 k 以外的
dis[i]的最小值(贪心)，假设最小值对应的节点是 3。此时可以断言：dis[3]已经是 k 到 3 的最短路长度，不可能有其它 k 到 3 的路径更短！反证法：假设存在更短的路径，那我们一定会从 k 出发经过一个点 u，它的dis[u]比dis[3]还要小，然后再经过一些边到达 3，得到更小的dis[3]。但dis[3]已经是最小的了，并且图中没有负数边权，所以 u 是不存在的，矛盾。故原命题成立，此时我们得到了dis[3]的最终值。 - 用节点 3 到其邻居 y 的边权
g[3][y]更新dis[y]：如果dis[3]+g[3][y]<dis[y]，那么更新dis[y]为dis[3]+g[3][y]，否则不更新。 - 然后取除了节点 k,3 以外的
dis[i]的最小值，重复上述过程。 - 由数学归纳法可知，这一做法可以得到每个点的最短路。当所有点的最短路都已确定时，算法结束。
2.模版
// 返回从起点start到每个点的最短路径dis,如果节点x不可达，则dis[x]=LLong_max
// 要求：没有负数边权
// 时间复杂度O(n+mlogm),注意堆中有O(m)个元素(懒更新所有边进入),获取堆元素每次为(logm)
// 两个节点之间也可能有多条边不用更改代码，同样满足
typedef long long ll;
typedef pair<int,long long> PIL;
typedef pair<long long,int> PLI;
vector<ll> shortPathDijkstra(int n,vector<vector<int>>& edges,int start){
// 注:如果节点编号从1开始(而不是从0开始)，可以把n加1(g初始化,dis初始化以及最终dis结果不包括0元素)
vector<vector<PIL>> g(n);
for(auto& e:edges){
int x=e[0],y=e[1],wt=e[2];
g[x].push_back({y,wt});
// g[y].push_back({x,wt}); // 无向图
}
vector<ll> dis(n,LLONG_MAX);
// 最短距离小顶堆
priority_queue<PLI,vector<PLI>,greater<>> pq;
dis[start]=0;
pq.push({0,start});
while(!pq.empty()){
auto t=pq.top();
pq.pop();
ll dis_x=t.first;
int x=t.second;
// 懒删除
if(dis_x>dis[x]){
continue;
}
for(auto& t2:g[x]){
int y=t2.first;
ll wt=t2.second;
ll newdis=dis_x+wt;
if(newdis<dis[y]){
dis[y]=newdis;
// 懒更新堆，先不更新堆中最短距离，而是全都入堆，出堆时再判断
pq.push({newdis,y});
}
}
}
return dis;
}
2.网格图模版(无邻接表，dis二维数组，堆中tuple三元组):
class Solution {
public:
int n, m;
typedef long long ll;
typedef tuple<long long, int, int> TLII;
vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
bool inMap(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
int minTimeToReach(vector<vector<int>>& moveTime) {
n = moveTime.size(), m = moveTime[0].size();
vector<vector<ll>> dis(n, vector<ll>(m, LLONG_MAX));
priority_queue<TLII, vector<TLII>, greater<>> pq;
dis[0][0] = 0;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
ll dis_xy = get<0>(t);
int x = get<1>(t), y = get<2>(t);
if (dis_xy > dis[x][y])
continue;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (!inMap(nx, ny))
continue;
ll newdis = max(dis_xy, 1LL * moveTime[nx][ny]) + 1;
if (newdis < dis[nx][ny]) {
dis[nx][ny] = newdis;
pq.push({newdis, nx, ny});
}
}
}
return dis[n - 1][m - 1];
}
};
2.题目描述
3.学习经验
1. 743. 网络延迟时间(中等)
思想
1.有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
2.模版题，时间即边权，答案为起点到其他点的最大距离
代码
class Solution {
public:
typedef long long ll;
typedef pair<int, long long> PIL;
typedef pair<long long, int> PLI;
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<PIL>> g(n + 1);
for (auto& e : times) {
int u = e[0], v = e[1], wt = e[2];
g[u].push_back({v, wt});
}
vector<ll> dis(n + 1, LLONG_MAX);
priority_queue<PLI, vector<PLI>, greater<>> pq;
dis[k] = 0;
pq.push({0, k});
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
int u = t.second;
ll dis_u = t.first;
if (dis_u > dis[u])
continue;
for (auto& t2 : g[u]) {
int y = t2.first;
ll wt = t2.second;
if (dis_u + wt < dis[y]) {
dis[y] = dis_u + wt;
pq.push({dis[y], y});
}
}
}
ll res = -1;
for (int i = 1; i <= n; ++i) {
if (dis[i] == LLONG_MAX)
return -1;
res = max(res, dis[i]);
}
return res;
}
};
2. 3341. 到达最后一个房间的最少时间I(中等)
3341. 到达最后一个房间的最少时间 I - 力扣（LeetCode）
思想
1.有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。
给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示房间开启并可达所需的 最小 秒数。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为 1 秒。
请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。
2.网格图Dijkstra,不再是单个顶点编号，而是一个位置，所以dis变成二维数组，堆中为三元组，可以用tuple<ll,int,int>,但获取元素不再是first,second,而是get<0>(t),get<1>(t),get<2>(t)
3.多了个限制条件:“其中 moveTime[i][j] 表示房间开启并可达所需的 最小 秒数”,所以从(x,y)到(nx,ny)的最少秒数为max(dis_xy,moveTime[nx][ny])+1
代码
class Solution {
public:
int n, m;
typedef long long ll;
typedef tuple<long long, int, int> TLII;
vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
bool inMap(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
int minTimeToReach(vector<vector<int>>& moveTime) {
n = moveTime.size(), m = moveTime[0].size();
vector<vector<ll>> dis(n, vector<ll>(m, LLONG_MAX));
priority_queue<TLII, vector<TLII>, greater<>> pq;
dis[0][0] = 0;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
ll dis_xy = get<0>(t);
int x = get<1>(t), y = get<2>(t);
if (dis_xy > dis[x][y])
continue;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (!inMap(nx, ny))
continue;
ll newdis = max(dis_xy, 1LL * moveTime[nx][ny]) + 1;
if (newdis < dis[nx][ny]) {
dis[nx][ny] = newdis;
pq.push({newdis, nx, ny});
}
}
}
return dis[n - 1][m - 1];
}
};
3. 3112. 访问消失节点的最少时间(中等)
3112. 访问消失节点的最少时间 - 力扣（LeetCode）
思想
1.给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。
同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。
注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。
请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。
2.从x->y,获得到达y的newdis后，先判断是否在disappear[y]之前即可
代码
class Solution {
public:
typedef pair<int, int> PII;
vector<int> minimumTime(int n, vector<vector<int>>& edges,
vector<int>& disappear) {
vector<vector<PII>> g(n);
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
priority_queue<PII, vector<PII>, greater<>> pq;
vector<int> dis(n, INT_MAX);
dis[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
int dis_u = t.first;
int u = t.second;
if (dis_u > dis[u])
continue;
for (auto& t2 : g[u]) {
int v = t2.first;
int w = t2.second;
int newdis = dis_u + w;
if (newdis < disappear[v] && newdis < dis[v]) {
dis[v] = newdis;
pq.push({newdis, v});
}
}
}
for (int i = 0; i < n; ++i) {
if (dis[i] == INT_MAX)
dis[i] = -1;
}
return dis;
}
};
二. 全源最短路：Floyd 算法
1.套路
1.Floyd 算法本质是三维 DP,理解:
f[k][i][j]表示i和j之间可以通过编号为1-k的节点集的最短路径
初值f[0][i][j]为原图的邻接矩阵
则f[k][i][j]:
- (1)从
f[k-1][i][j]转移过来，表示不经过k - (2)从
f[k-1][i][k]+f[k-1][k][j]转移过来，表示经过k
所以,f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])
发现最外层f[k]只由f[k-1]转移，所以可以覆盖，所以代码中只有写二维数组，但最外层遍历是k
![[floyd三维DP.png]]
2.图解为什么遍历时k在最外层，不能再最里层
(1)在最里层的反例(当前路径需要之后遍历的路径转移过来，即转移顺序与遍历顺序相斥):
![[floyd的k在内层反例.png]]
(2)k在最外层的更新逻辑(交换两个k作对比):
![[floyd的k在最外层.png]]
3.模版:
// 返回一个二维列表(邻接矩阵)，其中(i,j)这一项表示从i到j的最短路长度
// 如果无法从i到j，则最短路长度为LLONG_MAX/2(防止加法溢出)
// 允许负数边权
// 如果计算完毕后，存在i，使得从i到i的最短路长度小于0(负环找不到最短路，无限更新),说明图中有负环
// 节点编号从0到n-1
// 时间复杂度O(nn^3+m),其中m是edges的长度
typedef long long ll;
const ll INF=LLONG_MAX/2; // 防止加法溢出
vector<vector<ll>> shortestPathFloyd(int n,vector<vector<int>>& edges){
vector<vector<ll>> f(n,vector<ll>(n,INF));
for(int i=0;i<n;++i){
f[i][i]=0;
}
for(auto& e:edges){
int x=e[0],y=e[1];
ll w=e[2];
f[x][y]=min(f[x][y],w); // 如果有重边，取最小值
f[y][x]=min(f[y][x],w); // 无向图
}
// 三层遍历，最外层k
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
// 针对稀疏图的优化
if(f[i][k]==INF){
continue;
}
for(int j=0;j<n;++j){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
/*
// 检查负环
for(int i=0;i<n;++i){
if(f[i][i]<0){
// 存在负环
}
}
*/
return f;
}
2.题目描述
3.学习经验
1. 1334. 阈值距离内邻居最少的城市(中等)
1334. 阈值距离内邻居最少的城市 - 力扣（LeetCode）
思想
1.有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回在路径距离限制为 distanceThreshold 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
2.模版题
代码
class Solution {
public:
typedef long long ll;
const ll INF = LLONG_MAX / 2;
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
vector<vector<ll>> f(n, vector<ll>(n, INF));
for (int i = 0; i < n; ++i)
f[i][i] = 0;
for (auto& e : edges) {
int x = e[0], y = e[1], w = e[2];
f[x][y] = min(f[x][y], 1LL * w);
f[y][x] = min(f[y][x], 1LL * w);
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
if (f[i][k] == INF)
continue;
for (int j = 0; j < n; ++j) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
int res = -1, resCnt = INT_MAX;
// 倒序保证编号最大
for (int i = n - 1; i >= 0; --i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (f[i][j] <= distanceThreshold)
++cnt;
}
if (cnt < resCnt) {
resCnt = cnt;
res = i;
}
}
return res;
}
};
2. 2642. 设计可以求最短路径的图类(困难,学习)
2642. 设计可以求最短路径的图类 - 力扣（LeetCode）
思想
1.给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。
请你实现一个 Graph 类：
Graph(int n, int[][] edges)初始化图有n个节点，并输入初始边。addEdge(int[] edge)向边集中添加一条边，其中edge = [from, to, edgeCost]。数据保证添加这条边之前对应的两个节点之间没有有向边。int shortestPath(int node1, int node2)返回从节点node1到node2的路径 最小 代价。如果路径不存在，返回-1。一条路径的代价是路径中所有边代价之和。
2.首先能想到Dijkstra,初始化要O(n+m),addEdge要O(1),查询要O(n+mlogm)
学习Floyd,初始化要O(n3+m),**`addEdge`要O(n2),但是查询只要O(1)**
3.重点学习addEdge,即新增一条x->y,它会影响所有i->j的最短路，会出现i->…x->y…->j,所以二重循环更新
4.注意因为有f[i][x] + w + f[y][j],所以INF开INT_MAX / 3
代码
class Graph {
public:
vector<vector<int>> f;
const int INF = INT_MAX / 3;
int len;
Graph(int n, vector<vector<int>>& edges) {
len = n;
f.assign(n, vector<int>(n, INF));
for (int i = 0; i < n; ++i)
f[i][i] = 0;
for (auto& e : edges) {
int x = e[0], y = e[1], w = e[2];
f[x][y] = min(f[x][y], w);
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
if (f[i][k] == INF)
continue;
for (int j = 0; j < n; ++j) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
}
void addEdge(vector<int> edge) {
int x = edge[0], y = edge[1], w = edge[2];
if (w >= f[x][y]) { // 无需更新
return;
}
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
f[i][j] = min(f[i][j], f[i][x] + w + f[y][j]);
}
}
}
int shortestPath(int node1, int node2) {
if (f[node1][node2] == INF)
return -1;
else
return f[node1][node2];
}
};
/**
* Your Graph object will be instantiated and called as such:
* Graph* obj = new Graph(n, edges);
* obj->addEdge(edge);
* int param_2 = obj->shortestPath(node1,node2);
*/
3. 1462. 课程表IV(中等，floyd可以作为初始化，多次查询判断多源点是否可达，不是只能求最短距离)
思想
1.你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。
- 有的课会有直接的先修课程，比如如果想上课程
1，你必须先上课程0，那么会以[0,1]数对的形式给出先修课程数对。
先决条件也可以是 间接 的。如果课程a是课程b的先决条件，课程b是课程c的先决条件，那么课程a就是课程c的先决条件。
你也得到一个数组queries，其中queries[j] = [uj, vj]。对于第j个查询，您应该回答课程uj是否是课程vj的先决条件。
返回一个布尔数组answer，其中answer[j]是第j个查询的答案。
2.首先，这一问乍一眼看是拓扑排序，但拓扑排序是获得个顺序，而此题核心在于多次查询两个点是否可达，要简化查询的时间。从而多源点想到floyd,其作为初始化时间复杂度为O(n^3),但是查询只需O(1),所以非常合适，将边权简单设置为1即可，只要最短距离不是INF,说明可达。
代码
class Solution {
public:
const int INF = INT_MAX / 2;
vector<bool> checkIfPrerequisite(int numCourses,
vector<vector<int>>& prerequisites,
vector<vector<int>>& queries) {
vector<vector<int>> f(numCourses, vector<int>(numCourses, INF));
for (int i = 0; i < numCourses; ++i) {
f[i][i] = 0;
}
for (auto& e : prerequisites) {
int x = e[0], y = e[1];
f[x][y] = 1; // 假设边权位1
}
for (int k = 0; k < numCourses; ++k) {
for (int i = 0; i < numCourses; ++i) {
if (f[i][k] == INF)
continue;
for (int j = 0; j < numCourses; ++j) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
vector<bool> res;
for (auto& q : queries) {
int x = q[0], y = q[1];
// 利用floyd求出来的f数组判断是否可达
if (f[x][y] == INF)
res.push_back(false);
else
res.push_back(true);
}
return res;
}
};