数据结构与算法：图论——最短路径

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有 (ui, vi) 对都 互不相同（即，不含重复边）

//  floyed 算法
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));for (auto a : times) {dp[a[0]][a[1]] = a[2];}for (int i = 0; i <= n; i++) {dp[i][i] = 0;}for (int k = 0; k <= n; k++) {for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {if (dp[i][j] > dp[i][k] + dp[k][j]) {dp[i][j] = dp[i][k] + dp[k][j];}}}}int res = 0;for (int i = 1; i <= n; i++) {if (dp[k][i] == INT_MAX / 2)return -1;res = max(res, dp[k][i]);}return res;}
};

• 这个用floyed直接算即可。无向图构造矩阵时重复操作即可

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

示例 1：

输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2] 
城市 1 -> [城市 0, 城市 2, 城市 3] 
城市 2 -> [城市 0, 城市 1, 城市 3] 
城市 3 -> [城市 1, 城市 2] 
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。

示例 2：

输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。 
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1] 
城市 1 -> [城市 0, 城市 4] 
城市 2 -> [城市 3, 城市 4] 
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3] 
城市 0 在阈值距离 2 以内只有 1 个邻居城市。

class Solution {
public:int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));for (auto a : edges) {dp[a[0]][a[1]] = a[2];dp[a[1]][a[0]] = a[2];}for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (dp[i][j] > dp[i][k] + dp[k][j])dp[i][j] = dp[i][k] + dp[k][j];// floyed计算完毕，取次数判断即可vector<int> cnt(n, 0);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j)continue;if (dp[i][j] <= distanceThreshold)cnt[i]++;}}int min = *min_element(cnt.begin(), cnt.end());int res;for (int i = n - 1; i >= 0; i--) {if (min == cnt[i]) {res = i;break;}}return res;}
};

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

// BellmanFord算法  算法复杂度为O（m*n）
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dp(n+1,INT_MAX/2);dp[k ] = 0;bool flag;while(1){flag = true;// vector<int> predp(dp);for(auto a:times){if(dp[a[1]] > dp[a[0]]+a[2]){flag = false;dp[a[1]] = dp[a[0]]+a[2];}}if(flag) break;}int res = *max_element(dp.begin()+1,dp.end());return res==INT_MAX/2?-1:res;}
};

• 经典使用BellmanFord算法题目：最多经过 k 站中转的路线

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，图中蓝色所示。

提示：

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 104
• 航班没有重复，且不存在自环
• 0 <= src, dst, k < n
• src != dst

/*BellmanFord算法:：外层的路径就是中转的次数，但是注意K++；是中转1此，那么可以使用两条路径使用BellmanFord算法最标准形式：使用predp形式
*/
class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {vector<int> dp(n, 1e5+1);dp[src] = 0;k++;while (k--) {vector<int> predp(dp);// 这里最好加&可以大大提高速度for (auto &a : flights) {if(dp[a[1]]>predp[a[0]]+a[2])dp[a[1]] =predp[a[0]]+a[2];}}return dp[dst] ==  1e5+1? -1 : dp[dst];}
};
/*不使用BellmanFord算法最标准形式：无predp形式无法准确得到中转次数：结果不对，但是不考虑次数的话，也能得到最短距离
*/// 结果不对
class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,int k) {vector<int> dp(n, 1e5+1);dp[src] = 0;k++;while (k--) {// vector<int> predp(dp);for (auto &a : flights) {if(dp[a[1]]>dp[a[0]]+a[2])dp[a[1]] =dp[a[0]]+a[2];}}return dp[dst] ==  1e5+1? -1 : dp[dst];}
};

• 本题重点是无向图：两边都要操作一次，重复操作即可
• 无向图：说白了就是条件是有向图的两倍，给反转前后节点即可

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25

示例 2：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000

示例 3：

输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径

提示：

• 2 <= n <= 10^4
• 0 <= start, end < n
• start != end
• 0 <= a, b < n
• a != b
• 0 <= succProb.length == edges.length <= 2*10^4
• 0 <= succProb[i] <= 1
• 每两个节点之间最多有一条边

class Solution {
public:double maxProbability(int n, vector<vector<int>>& edges,vector<double>& succProb, int start_node,int end_node) {vector<double> dp(n, 0);dp[start_node] = 1;while (1) {bool flag = true;for (int i = 0; i < succProb.size(); i++) {// 双向图：反转前后再操作一次即可if (dp[edges[i][1]] < dp[edges[i][0]] * succProb[i]) {flag = false;dp[edges[i][1]] = dp[edges[i][0]] * succProb[i];}if (dp[edges[i][0]] < dp[edges[i][1]] * succProb[i]) {flag = false;dp[edges[i][0]] = dp[edges[i][1]] * succProb[i];}}if (flag)   break;}return dp[end_node];}
};

• 这个用floyed直接算即可。使用bellmanFord可以做

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

示例 1：

输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2] 
城市 1 -> [城市 0, 城市 2, 城市 3] 
城市 2 -> [城市 0, 城市 1, 城市 3] 
城市 3 -> [城市 1, 城市 2] 
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。

示例 2：

输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。 
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1] 
城市 1 -> [城市 0, 城市 4] 
城市 2 -> [城市 3, 城市 4] 
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3] 
城市 0 在阈值距离 2 以内只有 1 个邻居城市。

class Solution {
public:int targetnum(int n, vector<vector<int>>& edges, int distanceThreshold,int k) {vector<int> dp(n, INT_MAX / 2);dp[k] = 0;while (1) {bool flag = true;vector<int> predp(dp);for (auto& a : edges) {if (dp[a[1]] > predp[a[0]] + a[2]) {flag = false;dp[a[1]] = predp[a[0]] + a[2];}if (dp[a[0]] > predp[a[1]] + a[2]) {flag = false;dp[a[0]] = predp[a[1]] + a[2];}}if (flag)break;}int res = 0;/*这里注意：这个是排除本身for (int i = 0; i < n; i++) {if (i == k)continue;if (dp[i] <= distanceThreshold) {res++;}}若改成：只要碰到i!=k，则跳出这个for循环，后面都不执行了for (int i = 0; i < n && i!=k; i++) {if (dp[i] <= distanceThreshold) {res++;}}*/for (int i = 0; i < n; i++) {if (i == k)continue;if (dp[i] <= distanceThreshold) {res++;}}return res;}// 找到最右边的最小值及坐标。int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {int min_num = 200;int res = 0;for(int i = 0;i<n;i++){int mid = BellmabFord( n, edges, i, distanceThreshold);if(mid<=min_num){min_num = mid;res = i; }}return res;}// 直观但臃肿。int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {int minn = INT_MAX / 2;vector<int> res;for (int i = 0; i < n; i++) {res.push_back(targetnum(n, edges, distanceThreshold, i));}int sul = 0;int minnub = *min_element(res.begin(), res.end());for (int i = n - 1; i >= 0; i--) {if (res[i] == minnub) {sul = i;break;}}return sul;}
};

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有 (ui, vi) 对都 互不相同（即，不含重复边）

/*普通版本
*/class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dp(n + 1, INT_MAX / 2);dp[k] = 0;vector<vector<int>> dis(n + 1, vector<int>(n + 1, INT_MAX / 2));for (auto& a : times) {dis[a[0]][a[1]] = a[2];}vector<int> visited(n + 1, false);//for(int i = 0;i<=n;i++){while(1) {int blue = 0;for (int i = 0; i <= n; i++) {if (!visited[i] && dp[blue] > dp[i]) {blue = i;}}// 再次遇到说明最小值就是0了，结束了if(visited[blue]) break;visited[blue] = true;for (int i = 0; i <= n; i++) {if (dp[i] > dp[blue] + dis[blue][i]) {dp[i] = dp[blue] + dis[blue][i];}}}int res = *max_element(dp.begin() + 1, dp.end());return res == INT_MAX / 2 ? -1 : res;}
};// 堆优化版本
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;//	que.push({k,0});que.push({0, k});vector<bool> visited(n + 1, false);vector<int> dp(n + 1, INT_MAX / 2);dp[k] = 0;while (!que.empty()) {auto blue = que.top();que.pop();// 这里不用想那么多：看见置true直接在前面加判断if( visited[blue.second]) continue;visited[blue.second] = true;for (auto& a : times) {// 这里直接取头节点不是这个blue的直接跳过，已经为白的直接跳过// 目的是为了取最小的蓝if (a[0] != blue.second || visited[a[1]] )continue;if (dp[a[1]] > dp[blue.second] + a[2]) {dp[a[1]] = dp[blue.second] + a[2];que.push({dp[a[1]], a[1]});}}}int res = *max_element(dp.begin() + 1, dp.end());return res == INT_MAX / 2 ? -1 : res;}
};

• 直接使用堆优化：注意双向图即可

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

示例 1：

输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2] 
城市 1 -> [城市 0, 城市 2, 城市 3] 
城市 2 -> [城市 0, 城市 1, 城市 3] 
城市 3 -> [城市 1, 城市 2] 
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。

示例 2：

输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。 
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1] 
城市 1 -> [城市 0, 城市 4] 
城市 2 -> [城市 3, 城市 4] 
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3] 
城市 0 在阈值距离 2 以内只有 1 个邻居城市。

/*无向图的堆优化djikstra算法：
*/
class Solution {
public:int target(int n, vector<vector<int>>& edges, int distanceThreshold,int k) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;que.push({0, k});vector<int> dis(n, INT_MAX / 2);dis[k] = 0;vector<bool> visited(n, false);while (!que.empty()) {int blue = que.top().second;que.pop();if (visited[blue])continue;visited[blue] = true;for (auto& a : edges) {if (a[0]==blue && dis[a[1]] > dis[a[0]] + a[2]) {dis[a[1]] = dis[a[0]] + a[2];que.push({dis[a[1]], a[1]});}if (a[1]==blue && dis[a[0]] > dis[a[1]] + a[2]) {dis[a[0]] = dis[a[1]] + a[2];que.push({dis[a[0]], a[0]});}}}int res = 0;for (auto& a : dis) {if (a <= distanceThreshold)res++;}return res;}int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {int res = INT_MAX / 2;int resdex = 0;for (int i = 0; i < n; i++) {int mid = target(n, edges, distanceThreshold, i);if (mid <= res) {res = mid;resdex = i;}}return  resdex;}
};