重建两个顶点之间的多个最短路径的路径 [英] Reconstructing the paths for multiple shortest paths between 2 vertices

问题描述

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

I'm trying to write an algorithm which will reconstruct the shortest path/s (multiple paths tied for the shortest if there are any) between all pairs of vertices in the Floyd-Warshall algorithm. I took some hints from the question here: https://stackoverflow.com/a/11371588/7447425

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

Based on this, I've modified the Floyd-Warshall algorithm:

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

该图形采用边列表的形式，例如:

The graph is in the form of edge-list for e.g.,:

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)

到目前为止，一切似乎都运转良好.

Everything seems to be working well till this point.

对于路径重建，

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函数(或编写一个更有效的函数)，以便我可以获取每对顶点之间的所有最短路径(为最短路径绑定的路径)?

But this isn't working. So, can anyone kindly rectify the getpath function (or write a more efficient one) so that I can get all the shortest paths (paths tied for shortest paths) between every pair of vertices?

对于上面的图形，我有

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

这是准确的，但是通过它进行路径重建变得很麻烦.

which is accurate, but path reconstruction through this is becoming quite a hassle.

推荐答案

以下是我对您的函数所做的更改.

Here are the changes I made to your function.

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

1. I renamed next to next_node because next is actually a Python keyword.
2. I renamed dist to cost to be more descriptive.
3. I stored next_node as a set() to avoid having the same element added twice.
4. I made sure to make a new set() when paths lead through k. That is to avoid unintentional data aliasing. Your code had a bug where if the route from 1 - 3 - 2 matches 1 - 4 - 2 that you alias next[1][2] to next[1][3] then add 4 to it, which could be wrong for next[1][3].
5. I took into account the fact that your format allows multiple edges between nodes.

这给了我以下与您非常相似的功能:

This gave me the following function that is very similar to yours:

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 作为迭代器.这使其非常简单.两点之间也可能有很多很多路径，并且在这种情况下，迭代器可以避免使用过多的内存.而且，如果需要，您总是可以非常轻松地将其从迭代器转换为数组.这是该功能:

I then wrote all_paths as an iterator. This made it very simple. It is also possible that there will be many, many paths between two points, and an iterator avoids using too much memory in that case. And if you want, you can always turn it from an iterator into an array very easily. Here is that function:

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

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

And here is some test code to demonstrate it:

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

这篇关于重建两个顶点之间的多个最短路径的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！