2959.力扣每日一题7/17 Java（暴力枚举+Floyd算法）
目录
Floyd算法
Floyd 算法又称为弗洛伊德算法、插点法，是一种用于解决给定加权图中顶点间最短路径的算法。它可以正确处理有向图或带有负权边的最短路径问题，同时也可用于计算有向图的传递闭包。该算法以其创始人之一、1978 年图灵奖获得者罗伯特·弗洛伊德命名。
其核心思路是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。具体来说，从图的带权邻接矩阵开始，递归地进行多次更新。其状态转移方程为：
map(i, j) := min{map(i, k) + map(k, j), map(i, j)}，其中map(i, j)表示 i 到 j 的最短距离，k 是穷举 i, j 的断点。
算法过程大致如下：
- 初始化：将距离矩阵 d(u, v)初始化为图的权值矩阵 a(u, v)。如果两点之间没有边相连，则权为无穷大（或一个足够大的数）。同时，初始化一个后继节点矩阵 path 来记录两点间的最短路径，d(i, j)初始化为 j。
- 迭代更新：进行 n 次更新（n 为图中顶点的数量）。对于每一对顶点 u 和 v，遍历所有的顶点 k，判断是否存在一个顶点 k 使得从 u 到 k 再到 v 比已知的路径更短。如果是，则更新距离矩阵 d(u, v)的值为 d(u, k) + d(k, v)，同时更新后继节点矩阵 path(u, v)为 k。
- 最终得到的距离矩阵 d 中的元素 d(i, j)即为 i 号顶点到 j 号顶点的最短路径长度，而后继节点矩阵 path 中则包含了最短路径的信息。
Floyd 算法的时间复杂度为，其中 n 是图中顶点的数量。它的优点是容易理解，可以算出任意两个节点之间的最短距离，代码编写相对简单；缺点是时间复杂度较高，不太适合处理大量数据的情况。
在上述提到的问题中，使用 Floyd 算法来计算各个顶点之间的最短路径，通过三重循环遍历所有可能的中转顶点 k，以及起点 i 和终点 j，根据状态转移方程不断更新距离矩阵 f，以得到最终的最短路径信息。
解题思路
通过枚举所有可能的节点集合状态，对于每个状态，复制相关节点的距离信息到一个临时矩阵，然后在这个子集上运行 Floyd 算法计算最短路，最后检查这个子集中任意两个节点的最短路是否都不超过给定的最大距离，统计满足条件的方案数。
解题过程
- 首先初始化距离矩阵，根据道路信息更新矩阵中的距离值。
- 然后通过两层循环枚举所有可能的节点集合状态。
- 对于每个状态，复制相关节点的距离信息到临时矩阵，并在这个子集上运行 Floyd 算法更新最短距离。
- 最后检查这个子集内的最短距离是否都满足不超过最大距离的条件，若是则方案数加 1。
时间复杂度
- 首先初始化距离矩阵，根据道路信息更新矩阵中的距离值。
- 然后通过两层循环枚举所有可能的节点集合状态。
- 对于每个状态，复制相关节点的距离信息到临时矩阵，并在这个子集上运行 Floyd 算法更新最短距离。
- 最后检查这个子集内的最短距离是否都满足不超过最大距离的条件，若是则方案数加 1。
空间复杂度
- 保存距离矩阵和临时矩阵的空间复杂度为 O(n^2)。
- 总的空间复杂度为 O(n^2)。
Code
import java.util.Arrays;
class Solution {
public int numberOfSets(int numNodes, int maxDist, int[][] roadDetails) {
// 创建并初始化距离矩阵 distanceMatrix
int[][] distanceMatrix = new int[numNodes][numNodes];
for (int[] row : distanceMatrix) {
Arrays.fill(row, Integer.MAX_VALUE / 2); // 防止加法溢出
}
// 根据道路信息更新距离矩阵
for (int[] road : roadDetails) {
int nodeA = road[0];
int nodeB = road[1];
int weight = road[2];
distanceMatrix[nodeA][nodeB] = Math.min(distanceMatrix[nodeA][nodeB], weight);
distanceMatrix[nodeB][nodeA] = Math.min(distanceMatrix[nodeB][nodeA], weight);
}
int solutionCount = 0;
int[][] tempDistanceMatrix = new int[numNodes][numNodes];
for (int nodeSetState = 0; nodeSetState < (1 << numNodes); nodeSetState++) {
for (int node = 0; node < numNodes; node++) {
if (((nodeSetState >> node) & 1) == 1) {
System.arraycopy(distanceMatrix[node], 0, tempDistanceMatrix[node], 0, numNodes);
}
}
// Floyd 算法（只考虑当前节点集合状态中的节点）
for (int intermediateNode = 0; intermediateNode < numNodes; intermediateNode++) {
if (((nodeSetState >> intermediateNode) & 1) == 0) continue;
for (int sourceNode = 0; sourceNode < numNodes; sourceNode++) {
if (((nodeSetState >> sourceNode) & 1) == 0) continue;
for (int destinationNode = 0; destinationNode < numNodes; destinationNode++) {
tempDistanceMatrix[sourceNode][destinationNode] = Math.min(tempDistanceMatrix[sourceNode][destinationNode], tempDistanceMatrix[sourceNode][intermediateNode] + tempDistanceMatrix[intermediateNode][destinationNode]);
}
}
}
// 判断当前保留的节点之间的最短路是否均不超过最大距离
boolean validSet = true;
for (int nodeA = 0; nodeA < numNodes; nodeA++) {
if (((nodeSetState >> nodeA) & 1) == 0) continue;
for (int nodeB = 0; nodeB < nodeA; nodeB++) {
if (((nodeSetState >> nodeB) & 1) == 1 && tempDistanceMatrix[nodeA][nodeB] > maxDist) {
validSet = false;
continue;
}
}
}
if (validSet) {
solutionCount++;
}
}
return solutionCount;
}
}
思想永远是宇宙的统治者。——柏拉图（Plato）
原文地址：https://blog.csdn.net/Rangsh/article/details/140552646
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！