>上下文
我目前正在研究我的一些图算法中的路径重建。对于单源最短路径问题，我使用了一系列前置节点来重建从一个源节点到所有其他节点的最短路径。
快速示例：[0， 3， 0， 0]
从源 0 到目标 1 的最短路径是 [0， 3， 1]，因为从目标节点 1 开始，可以使用"父"数组向后构造路径。 已超过 3 达到 1，超过 0 达到 3。 0 是源。做。
接下来的算法是全对最短路径算法。最简单的例子是Floyd-Warshall算法，它产生了一个包含所有"后继"节点的矩阵。重建伪代码的一个很好的例子可以在维基百科上找到 - Floyd Warshall。 总结一下：矩阵用于存储来自一个特定源节点的每个后续节点。它基本上遵循与以前相同的方法，只是将每个节点作为源，并且向前而不是向后。
问题 - 在伪乘法算法的情况下，如何创建后继矩阵？
我们先来看看算法：
for(int m = 0; m < nodeCount - 1; m++) {
Matrix nextResultMatrix = new Matrix(nodeCount, nodeCount, Integer.MAX_VALUE);
for(int i = 0; i < nodeCount; i++) {
for(int j = 0; j < nodeCount; j++) {
int value = Integer.MAX_VALUE;
for(int k = 0; k < nodeCount; k++) {
value = Math.min(
value,
resultMatrix.at(i, k) + sourceMatrix.at(k, j)
);
}
nextResultMatrix.setAt(i, j, value);
}
}
resultMatrix = nextResultMatrix;
}
在每次迭代中，将计算长度为 m 的最短路径的矩阵。内部循环与矩阵乘法本身非常相似。在最内部的循环中，算法检查当前路径是否短于从源 i 到 k 到目标 j 的路径。内部 k 循环完成后，将设置新结果矩阵内部的值。这导致了问题：
在Floyd-Warshall算法的情况下，更容易识别路径是否更短以及哪个节点现在是继任者。在这种情况下，无论如何都会设置在 k 循环中计算的值。是否可以在这里确定继任者？
关于可能的解决方案的想法
- 伪乘法算法为每次迭代提供了一个矩阵，该矩阵表示长度为 m 的最短路径.这可能有助于找到解决方案，而不会增加 - 已经相当糟糕的 - 时间复杂度，也不必同时存储每个矩阵。
- 我在关于堆栈溢出的评论中发现了一个有趣的想法，这可能会导致解决方案参考。从那里所说的情况来看，跟踪最短路径似乎是一项相当繁重的工作。不过，我还没有完全理解这个想法以及如何实现这一点。
我的解决方案
因此，在逐步完成算法并明确每一步的确切含义之后，我终于能够找到解决方案。我将尝试在此处解释代码中的更改，但首先让我提出解决方案：
for(int m = 0; m < nodeCount - 1; m++) {
Matrix nextResultMatrix = new Matrix(nodeCount, nodeCount, Integer.MAX_VALUE);
for(int i = 0; i < nodeCount; i++) {
for(int j = 0; j < nodeCount; j++) {
int value = resultMatrix.at(i, j);
int shorterPathFoundOverNode = prevMatrix.at(i, j);
// new shortest path from node i to j is
// the minimum path that can be found from node i over k to j
// k will be the node itself and every other node
for(int k = 0; k < nodeCount; k++) {
if(resultMatrix.at(i, k) != Graph.NO_EDGE && sourceMatrix.at(k, j) != Graph.NO_EDGE) {
if(value > resultMatrix.at(i, k) + sourceMatrix.at(k, j)) {
// update value if path is shorter
value = resultMatrix.at(i, k) + sourceMatrix.at(k, j);
shorterPathFoundOverNode = k;
}
}
}
nextResultMatrix.setAt(i, j, value);
prevMatrix.setAt(i, j, shorterPathFoundOverNode);
}
}
resultMatrix = nextResultMatrix;
}
一个非常基本但重要的思想是将 j 循环中值的初始化值从 Integer.MAX替换为以前找到的值或在第一次迭代时替换用于初始化矩阵的值 (Integer.MAX)。这也很重要，因为每次迭代的条件都会为真一次，这在以前不会引起任何问题，但现在 - 因为我们在条件内执行更多操作 - 这很重要。
有必要将 Math.min 方法替换为 if 条件，以便能够执行更多操作，而不仅仅是设置值。
为了重建最短路径，使用了跟踪先前节点的方法。这与问题中所述的单源最短路径问题非常相似。当然，在这种情况下需要使用矩阵，因为所有节点都将是源节点。
总结一下这个想法：设置一个额外的矩阵来跟踪每个目标节点的前一个节点。遍历 k 循环时，如果找到较短的路径，请保存前一个节点(重要提示：仅当它实际上比前一个路径短时)。