最短路径 | 743. 网络延迟时间之 Dijkstra 算法和 Floyd 算法

前言：我在做「399. 除法求值」时，看到了基于 Floyd 算法的解决方案，突然想起来自己还没有做过最短路径相关的题。因此找来了「743. 网络延迟时间」作为练习，其本质是在求解一个源点到其他各点的最短路径。

1 基于 Dijkstra 算法

假设源点为 $2$，那么手工模拟如下图所示：

代码的编写在本质上就是实现上述手工模拟过程。

1.1 代码说明

为了表示两点之间没有路径，我们定义两点之间的距离为无穷大：

const int inf = INT_MAX / 2;

说明：这里只是对 $\inf$ 进行定义，后面才会进行使用；为什么不直接定义为 $\inf =\mathrm{IN}{\mathrm{T}}_{-}\mathrm{MAX}$？因为在更新距离时涉及加法操作，而 $\mathrm{IN}{\mathrm{T}}_{-}\mathrm{MAX}$ 可能让加法越界，所以我们取其一半来表示无穷大。

Step1：构建图

由于题目通常给出的是边的起点、终点以及权值，而非存储了图结构的二维数组，因此无论是 Dijkstra 算法还是 Floyd 算法，我们都需要完成图的构建。代码如下：

vector<vector<int>> graph(n + 1, vector<int>(n + 1, inf));
for (auto & t : times)graph[t[0]][t[1]] = t[2];

逻辑非常简单：① 创建一个二维数组 $\mathrm{graph}$；② $\mathrm{graph}[\mathrm{i}][\mathrm{j}]$ 表示边 $<\mathrm{i},\mathrm{j}>$ 的权值。

说明：初始时如果两点之间没有边，那么认为两点之间的距离为 $\inf$ 无穷大。

Step2：定义数组

vector<int> dist(n + 1, inf);
dist[k] = 0;
vector<int> used(n + 1, 0);

• $\mathrm{dist}$ 数组用于存储每一轮源点 $\mathrm{k}$ 到其他点的距离；
• $\mathrm{used}$ 数组用于表明当前点是否已经被纳入集合。

说明：由于 $\mathrm{k}$ 到自己的距离为 $0$，因此有 $\mathrm{dist}[\mathrm{k}]=0$；为什么不直接让 $\mathrm{used}[\mathrm{k}]=1$？由于在纳入每个点时都会更新源点 $\mathrm{k}$ 到其他点的距离，因此我们在初始时并不直接将 $\mathrm{k}$ 纳入集合，而是放到后面和其他点统一处理，从而避免了需要在初始时更新 $\mathrm{dist}$ 数组的值的问题。

Step3：纳入并更新距离

for (int i = 1; i <= n; ++i) {// 查找距离源点最近的点int s = -1;for (int t = 1; t <= n; ++t) {if (!used[t] && (s == -1 || dist[s] > dist[t]))s = t;}// 纳入该点used[s] = 1;// 更新距离for (int j = 1; j <= n; ++j)dist[j] = min(dist[j], dist[s] + graph[s][j]);
}

其中 $\mathrm{s}$ 用于查找当前距离源点最近的点，$\mathrm{t}$ 用于遍历所有未被纳入的点。

说明：由于初始时只有 $\mathrm{dist}[\mathrm{k}]=0$，而其他距离被默认为 $\inf$ 无穷大，因此第一个被纳入的一定是源点 $\mathrm{k}$。

Step4：返回结果

由于题目提问「需要多久才能使所有节点都收到信号」，因此我们返回源点 $\mathrm{k}$ 到其他点的最短距离的最大值即可。代码如下：

int ans = * max_element(dist.begin() + 1, dist.end());
return ans == inf ? -1 : ans;

如果最大值是 $\inf$，那么说明源点 $\mathrm{k}$ 无法到达某些点，因此返回 $-1$。

1.2 完整代码

int networkDelayTime(vector<vector<int>>& times, int n, int k) {const int inf = INT_MAX / 2;vector<vector<int>> graph(n + 1, vector<int>(n + 1, inf));for (auto & t : times)graph[t[0]][t[1]] = t[2];vector<int> dist(n + 1, inf);dist[k] = 0;vector<int> used(n + 1, 0);for (int i = 1; i <= n; ++i) {int s = -1;for (int t = 1; t <= n; ++t) {if (!used[t] && (s == -1 || dist[s] > dist[t]))s = t;}used[s] = 1;for (int j = 1; j <= n; ++j)dist[j] = min(dist[j], dist[s] + graph[s][j]);}int ans = * max_element(dist.begin() + 1, dist.end());return ans == inf ? -1 : ans;
}

2 基于 Floyd 算法

说明：上图只是给出一个示例，并没有把整个更新过程画完整，请自行脑补。

2.1 代码说明

Step1：构建图（与 Dijkstra 算法一致）

Step2：更新距离

Floyd 算法的核心：不断尝试在点 $\mathrm{i}$ 和点 $\mathrm{j}$ 之间加入其他点 $\mathrm{k}$ 作为中间点，如果加入 $\mathrm{k}$ 之后的距离比加入 $\mathrm{k}$ 之前的距离短，那么就更新点 $\mathrm{i}$ 和点 $\mathrm{j}$ 之间的距离。重复上述操作 $\mathrm{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] >= 0 && graph[k][j] >= 0)graph[i][j] = graph[i][j] >= 0 ?min(graph[i][j], graph[i][k] + graph[k][j]): graph[i][k] + graph[k][j];}}
}

注意：中间点 $\mathrm{k}$ 必须在最外层循环，否则一些路径无法被更新到；为什么判断条件是 $>=0$？因为题目给出的边的权值的范围为 $[0,100]$，所以需要包含 $0$。

Step3：返回结果

int ans = -1;
for (int j = 1; j <= n; ++j) {if (graph[k][j] == -1 && k != j)return -1;else if (k != j)ans = max(ans, graph[k][j]);
}
return ans;

由于我们只需要源点 $\mathrm{k}$ 到其他点的距离，因此只需要遍历 $\mathrm{graph}$ 中的第 $\mathrm{k}$ 行。

说明：由于我们在本方案中定义两点之间没有路径时的边的权值为 $-1$，因此只要 $\mathrm{graph}[\mathrm{k}][\mathrm{j}]==-1$，就说明源点 $\mathrm{k}$ 无法到达点 $\mathrm{j}$，因此返回 $-1$。

2.2 完整代码

int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<int>> graph(n + 1, vector<int>(n + 1, -1));for (auto & t : times)graph[t[0]][t[1]] = t[2];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] >= 0 && graph[k][j] >= 0)graph[i][j] = graph[i][j] >= 0 ?min(graph[i][j], graph[i][k] + graph[k][j]): graph[i][k] + graph[k][j];}}}int ans = -1;for (int j = 1; j <= n; ++j) {if (graph[k][j] == -1 && k != j)return -1;else if (k != j)ans = max(ans, graph[k][j]);}return ans;
}

虽然 Floyd 算法写起来没有 Dijkstra 算法繁琐，但是针对该问题的时间复杂度更高。