Floyd-Warshall：所有最短路径 [英] Floyd-Warshall: all shortest paths

问题描述

我已经实现了Floyd-Warshall，以返回每对节点/顶点之间的最短路径的距离以及每对节点/顶点之间的单最短路径的距离。

I've implemented Floyd-Warshall to return the distance of the shortest path between every pair of nodes/vertices and a single shortest path between each of these pairs.

有没有办法让它返回每条最短的路径，即使对于每对节点，有多个最短的路径并列？ （我只是想知道我是否在浪费时间）

Is there any way to get it to return every shortest path, even when there are multiple paths that are tied for shortest, for every pair of nodes? (I just want to know if I'm wasting my time trying)

推荐答案

如果您只需要数多少种不同的计数存在最短路径，除了 shortestPath 数组之外，您还可以保留 count 数组。这是来自 Wiki 的伪代码的快速修改。 / p>

If you just need the count of how many different shortest path exist, you can keep a count array in addition to the shortestPath array. Here's is a quick modification of the pseudocode from wiki.

procedure FloydWarshall ()
    for k := 1 to n
        for i := 1 to n
            for j := 1 to n
                if path[i][j] == path[i][k]+path[k][j] and k != j and k != i
                    count[i][j] += 1;
                else if path[i][j] > path[i][k] + path[k][j]
                    path[i][j] = path[i][k] + path[k][j]
                    count[i][j] = 1

如果您需要找到所有路径的方法，则可以存储 vector / arraylist 像这样的结构，以使每对展开和折叠。这是来自同一 Wiki 的伪代码的修改。

If you need a way to find all the paths, you can store a vector/arraylist like structure for each pair to expand and collapse. Here is a modification of the pseudocode from the same wiki.

procedure FloydWarshallWithPathReconstruction ()
    for k := 1 to n
        for i := 1 to n
            for j := 1 to n
                if path[i][k] + path[k][j] < path[i][j]
                    path[i][j] := path[i][k]+path[k][j];
                    next[i][j].clear()
                    next[i][j].push_back(k) // assuming its a c++ vector
                else if path[i][k] + path[k][j] == path[i][j] and path[i][j] != MAX_VALUE and k != j and k != i
                    next[i][j].push_back(k)

注意：如果 k == j 或 k == i ，这意味着您正在检查 path [i] [i] + path [i] [ j] 或 path [i] [j] + path [j] [j] ，两者都应等于路径[i] [j] ，并且不会被压入 next [i] [j] 。

Note: if k==j or k==i, that means, you're checking either path[i][i]+path[i][j] or path[i][j]+path[j][j], both should be equal to path[i][j] and that does not get pushed into next[i][j].

路径重构应修改为处理 vector 。在这种情况下，计数将是每个个向量的大小。这是来自同一 Wiki 的伪代码（python）的修改版本a>。

Path reconstruction should be modified to handle the vector. The count in this case would be each vector's size. Here is a modification of the pseudocode (python) from the same wiki.

procedure GetPath(i, j):
    allPaths = empty 2d array
    if next[i][j] is not empty:
        for every k in next[i][j]:
            if k == -1: // add the path = [i, j]
                allPaths.add( array[ i, j] ) 
            else: // add the path = [i .. k .. j]
                paths_I_K = GetPath(i,k) // get all paths from i to k
                paths_K_J = GetPath(k,j) // get all paths from k to j
                for every path between i and k, i_k in paths_I_K:
                    for every path between k and j, k_j in paths_K_J:
                        i_k = i_k.popk() // remove the last element since that repeats in k_j
                        allPaths.add( array( i_k + j_k) )

    return allPaths

注意： path [i] [j] 是邻接表。在初始化 path [i] [j] 的同时，还可以通过添加来初始化 next [i] [j] -1 到数组。例如， next [i] [j] 的初始化将是

Note: path[i][j] is an adjacency list. While initializing path[i][j], you can also initialize next[i][j] by adding a -1 to the array. For instance an initialization of next[i][j] would be

for every edge (i,j) in graph:
   next[i][j].push_back(-1)

这要考虑到一条边本身就是最短的路径。您必须在路径重构中处理这种特殊情况，这就是我在 GetPath 中所做的事情。

This takes care of an edge being the shortest path itself. You'll have to handle this special case in the path reconstruction, which is what i'm doing in GetPath.

编辑： MAX_VALUE是距离数组中的初始化值。

"MAX_VALUE" is the initialized value in the array of distances.

这篇关于Floyd-Warshall：所有最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！