重建两个顶点之间的多条最短路径

Question

我正在尝试编写一个算法，该算法将重建Floyd-Warshall算法中所有顶点对之间的最短路径（如果有，则为最短路径绑定多条路径）。我从这个问题中得到了一些提示：https://stackoverflow.com/a/11371588/7447425

基于此，我修改了Floyd Warshall算法：

from math import inf

def floyd_warshall(n, edge):
    rn = range(n)
    dist = [[inf] * n for i in rn]
    next  = [[-1]   * n for i in rn]

    for i in rn:
        for j in rn:
            next[i][j]=[-1]

    for i in rn:
        dist[i][i] = 0

    for u, v, w in edge:
        dist[u][v] = w
        next[u][v]=[v]

    for k in rn:
        for i in rn:
            for j in rn:   
                sum_ik_kj = dist[i][k] + dist[k][j]
                if dist[i][j] > sum_ik_kj:
                   dist[i][j] = sum_ik_kj
                   next[i][j]=nxt[i][k]

                elif(sum_ik_kj==dist[i][j] and dist[i][j]!=inf and k!=j and k!=i):
                   next[i][j].extend(next[i][k])

return next

该图是边缘列表的形式，例如：

edge = [[0,2,2],[2,3,2],[3,1,1],[1,0,4],[1,2,3],[0,3,4],[3,0,5]]
# Here n is the value of the highest numbered-vertex. In the above graph, n=4
n=4
next=floyd_warshall(n,edge)

到目前为止，一切似乎都很顺利。

对于路径重建，

for i in range(n):
    for j in range(n):
        if(i!=j):
            allPaths=[]
            allPaths=getpath(i,j,next,allPaths)
            print(allPaths)

def getpath(i,j,nxt,allPaths):
    for k in next[i][j]:
        if(k==-1):
            allPaths.extend([i,j])

        elif(k==j):
            allPaths.append(j)

        else:
            paths_I_K=getpath(i,k,next,allPaths)
            paths_K_J=getpath(k,j,next,allPaths)
            for i_k in paths_I_K:
                for k_j in paths_K_J:
                    i_k.pop()
                    allPaths.append(i_k+k_j)
    return allPaths

但这不管用。那么，有没有人可以修改getpath函数（或者编写一个更有效的函数），这样我就可以得到每对顶点之间的所有最短路径（与最短路径绑定的路径）？

对于上面的图表，我有

next=
[[[-1], [3, 2], [2], [3, 2]],
 [[0], [-1], [2], [2]],
 [[3], [3], [-1], [3]],
 [[0, 1], [1], [1], [-1]]]

这是准确的，但通过它重建路径变得相当麻烦。

Answer 1

以下是我对你的功能所做的更改。

1. 我将next重命名为next_节点，因为next实际上是一个Python关键字
2. 我将dist重命名为cost，以便更具描述性
3. 我将next_node存储为set（），以避免将同一个元素添加两次
4. 当路径通过k时，我确保创建一个新的set（）。这是为了避免无意中的数据混淆。您的代码有一个错误，如果从1-3-2到next[1][2]的路径与您别名为next[1][2]到next[1][3]的路径匹配，则将4添加到该路径中，这对于next[1][3]可能是错误的
5. 我考虑到了这样一个事实，即您的格式允许节点之间有多条边

这给了我以下功能，这是非常相似的你：

def floyd_warshall(n, edge):
    rn = range(n)
    cost = [[inf] * n for i in rn]
    next_node = [[set() for j in rn] for i in rn]

    for i in rn:
        cost[i][i] = 0

    for u, v, w in edge:
        # The data format allows multiple edges between two nodes.
        if w < cost[u][v]:
            cost[u][v] = w
            next_node[u][v] = set([v])
        elif w == cost[u][v] and w < inf:
            next_node[u][v].add(v)

    for k in rn:
        for i in rn:
            for j in rn:
                cost_ik_kj = cost[i][k] + cost[k][j]
                if cost_ik_kj < cost[i][j]:
                    cost[i][j] = cost_ik_kj
                    next_node[i][j] = set(next_node[i][k]) # Want a copy.
                elif cost_ik_kj == cost[i][j] and cost_ik_kj < inf:
                    next_node[i][j].update( next_node[i][k] )

    return next_node

然后我以迭代器的形式编写了所有路径。这让事情变得非常简单。两点之间也可能有很多很多路径，在这种情况下，迭代器可以避免使用太多内存。如果你愿意，你可以很容易地把它从迭代器变成数组。以下是该函数：

def all_paths(next_node, i, j):
    if 0 == len(next_node[i][j]):
        if i == j:
            yield [j]
        else:
            pass # There is no path.
    else:
        for k in next_node[i][j]:
            for rest in all_paths(next_node, k, j):
                yield [i] + rest

下面是一些测试代码来演示：

edge = [[0,2,2],[2,3,2],[3,1,1],[1,0,4],[1,2,3],[0,3,4],[3,0,5]]
# Here n is the value of the highest numbered-vertex. In the above graph, n=4
n=4
next_node = floyd_warshall(n,edge)
for i in range(4):
    for j in range(4):
        for path in all_paths(next_node, i, j):
            print((i, j, path))