我正在尝试编写一种算法,该算法将在Floyd-Warshall算法的所有顶点对之间重建最短路径(多条路径,如果有的话,则为最短路径).我从这里的问题中得到了一些提示: stackoverflow/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: stackoverflow/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.
这给了我以下与您非常相似的功能:
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))更多推荐
重建两个顶点之间的多个最短路径的路径
发布评论