java - Floyd-Warshall算法返回权重相同的每条最短路径

如何使用Floyd-Warshall算法获得从顶点1到顶点10的每个具有相同权重的最短路径？
我设法获得了从顶点1到顶点10的所有最短路径的总数。

public static int[][] shortestpath(int[][] adj, int[][] path, int[][] count) {

    int n = adj.length;
    int[][] ans = new int[n][n];

    copy(ans, adj);

    // Compute incremently better paths through vertex k.
    for (int k = 0; k < n; k++) {

        // Iterate through each possible pair of points.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                // Check if it is better to go through k as an intermediate vertex.
                if (ans[i][k] + ans[k][j] < ans[i][j]) {
                    ans[i][j] = ans[i][k] + ans[k][j];
                    path[i][j] = path[k][j];
                    count[i][j] = count[i][k]*count[k][j];
                } else if ((ans[i][j] == ans[i][k]+ans[k][j]) && (k!=j) && (k!=i)) {
                    count[i][j] += count[i][k]*count[k][j];
                }
            }
        }
    }

    // Return the shortest path matrix.
    return ans;
}

public static void copy(int[][] a, int[][] b) {
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < a[0].length; j++)
            a[i][j] = b[i][j];
}

最佳答案

使用该算法一次即可找到距v1最短路径的每个顶点的加权长度。

再次使用该算法查找到v10的最短路径的每个顶点的加权长度。

最短路径上的所有顶点的两个加权长度之和等于从v1到v10的加权长度。如果且只有两个顶点都在最短路径上，且有向边缘的权重是与v1的加权长度之差，则有向边缘在最短路径上。

这将为您提供最短路径上所有内容的有向子图，其中大部分成本是基本算法的两次运行。您可以递归枚举。请注意，可能有很多最短的路径，因此枚举本身可能需要花费成倍的时间才能运行。

关于java - Floyd-Warshall算法返回权重相同的每条最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49884116/