algorithm - 路径重构——伪乘法(矩阵乘法)算法

Question

上下文

我目前正在研究我的一些图形算法中的路径重建。对于单源最短路径问题，我使用了一系列前辈来重建从一个源节点到所有其他节点的最短路径。

快速示例:[0, 3, 0, 0]

The shortest path from source 0 to target 1 would be [0, 3, 1] because starting from the target node 1 the path can be constructed by going backwards using the 'parent' array. 1 has been reached over 3 and 3 has been reached over 0. 0 is the source. Done.

---

接下来的算法是全对最短路径算法。最简单的例子是 Floyd-Warshall 算法，它产生一个包含所有“后继”节点的矩阵。重建伪代码的一个很好的例子可以在 Wikipedia - 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 的最短路径。这可能有助于在不增加(已经很糟糕的)时间复杂度且无需同时存储每个矩阵的情况下找到解决方案。
• 我在 stackoverflow 的评论中发现了一个有趣的想法，这可能会导致解决方案 reference .从那里所说的来看，跟踪最短路径似乎很繁重。不过，我还没有完全理解这个想法以及如何实现它。

Answer 1

我的解决方案

因此，在逐步完成算法并弄清楚每一步的确切含义后，我终于找到了解决方案。我将尝试在此处解释代码中的更改，但首先让我介绍解决方案:

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;
}

• 一个非常基本但重要的想法是将 Integer.MAX 中 j 循环内的值的初始化值替换为之前找到的值，或者在第一次迭代中替换为用于初始化矩阵的值(整数.MAX)。这一点也很重要，因为每次迭代条件都会为真一次，这在以前不会造成任何问题，但现在 - 因为我们在条件内执行更多操作 - 这很重要。

• 有必要将 Math.min 方法替换为 if 条件，以便能够做的不仅仅是设置值。

• 为了重建最短路径，使用了跟踪先前节点的方法。这与问题中所述的单源最短路径问题非常相似。当然这种情况下需要使用矩阵，因为所有的节点都是源节点。

To summarize the idea: Setup an additional matrix that keeps track of the previous node for each target node. When iterating through the k loop save the previous node if a shorter path has been found (Important: Only if it is actually shorter than the previous path).