Floyd-Warshall:所有最短的路径

Question

我实现了弗洛伊德-沃肖尔返回每对节点/顶点和一之间的最短路径的距离,单这些对之间的最短路径.

是否有任何方法可以让它返回每条最短路径,即使有多条路径都是最短路径,对于每对节点？(我只是想知道我是否在浪费时间去尝试)

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.这种情况下的计数是每个vector人的大小.这是来自同一个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]通过向-1数组添加a 来初始化.例如,初始化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.