algorithm - Floyd-Warshall：所有最短路径

Question

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

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

Answer 1

如果您只需要计算存在多少不同的最短路径，则可以在count数组之外保留一个shortestPath数组。这是对来自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的伪代码的修改。

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]，两者都应该等于path[i][j]并且不会被推入next[i][j]。

应该修改路径重建以处理vector. 在这种情况下，计数将是 eachvector的大小。这是来自同一个wiki的伪代码 (python) 的修改。

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]添加 a来进行初始化。-1例如，初始化next[i][j]将是

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

这会照顾边缘成为最短路径本身。您必须在路径重建中处理这种特殊情况，这就是我正在做的事情GetPath。

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

Answer 2

在某些情况下，当前批准的答案中的“计数”功能会失败。更完整的解决方案是：

procedure FloydWarshallWithCount ()
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]
                count[i][j] += count[i][k] * count[k][j]
            else if path[i][j] > path[i][k] + path[k][j]
                path[i][j] = path[i][k] + path[k][j]
                count[i][j] = count[i][k] * count[k][j]

这样做的原因是对于任何三个顶点 i、j 和 k，可能存在从 i 到 k 到 j 的多条最短路径。例如在图中：

       3             1
(i) -------> (k) ---------> (j)
 |            ^
 |            |
 | 1          | 1
 |     1      |
(a) -------> (b)

从 i 到 j 通过 k 有两条路径。count[i][k] * count[k][j]求从 i 到 k 的路径数，以及从 k 到 j 的路径数，并将它们相乘以求出路径 i -> k -> j 的数量。

Answer 3

投票最多的答案的补充：

1. 在GetPath函数中，命令

i_k = i_k.popk() // 删除最后一个元素，因为它在 k_j 中重复

应该向前移动一行，换句话说，进入paths_I_K的循环。

2. 在 GetPath 结束时，应删除重复的路径。

对应的 Python 代码如下，并检查了其正确性：

def get_all_shortest_paths_from_router(i, j, router_list, it=0):                                                                                                    
    all_paths = []
    if len(router_list[i][j]) != 0:
        for k in router_list[i][j]:
            if k == -1: # add the path = [i, j]
                all_paths.append([i, j])
            else: # add the path = [i .. k .. j]
                paths_I_K = get_all_shortest_paths_from_router(i,k,router_list,it+1) # get all paths from i to k
                paths_K_J = get_all_shortest_paths_from_router(k,j,router_list,it+1) # get all paths from k to j
                for p_ik in paths_I_K:
                    if len(p_ik) != 0:
                        p_ik.pop() # remove the last element since that repeats in k_j
                    for p_kj in paths_K_J:
                        all_paths.append(p_ik + p_kj)

    if it==0:
        all_paths.sort()
        all_paths = [all_paths[i] for i in range(len(all_paths)) if i == 0 or all_paths[i] != all_paths[i-1]]
    return all_paths