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

Question

我正在尝试编写一种算法，该算法将重建 Floyd-Warshall 算法中所有顶点对之间的最短 path/s（多条路径与最短路径相关联，如果有的话）。我从这里的问题中得到了一些提示：

基于此，我修改了 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

这是我对您的函数所做的更改。

我将 next 重命名为 next_node 因为 next 实际上是一个 Python 关键字。
为了更具描述性，我将 dist 重命名为 cost。
我将 next_node 存储为 set() 以避免将相同的元素添加两次。
当路径通过 k 时，我确保创建一个新的 set()。那是为了避免无意的数据别名。您的代码有一个错误，如果来自 1 - 3 - 2 的路由与您将 next[1][2] 别名为 next[1][3] 的 1 - 4 - 2 匹配，则向其添加 4，这可能是错误的next[1][3]。
我考虑到您的格式允许节点之间有多个边。

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

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

然后我写了all_paths作为一个迭代器。这使它变得非常简单。两点之间也有可能会有很多很多路径，迭代器会避免在这种情况下使用太多内存。如果你愿意，你总是可以很容易地将它从一个迭代器变成一个数组。这是该函数：

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))

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

Reconstructing the paths for multiple shortest paths between 2 vertices

algorithm

python-3.x

floyd-warshall