一. 单源最短路：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. 网络延迟时间(中等)

743. 网络延迟时间 - 力扣（LeetCode）

思想

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); // 无向图}// 三层遍历，最外层kfor(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(n^{3+m),**`addEdge`要O(n}2),但是查询只要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;elsereturn 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);elseres.push_back(true);}return res;}
};