python的networkx 算法_python-Igraph / networkx中的k最短路径实现(日元算法)

经过深入研究并基于this,this等,我建议实现k最短路径算法,以便在大型无向,循环加权图中找到第一,第二,第三…第k个最短路径.大约2000个节点.

Wikipedia上的伪代码是这样的：

function YenKSP(Graph, source, sink, K):

//Determine the shortest path from the source to the sink.

A[0] = Dijkstra(Graph, source, sink);

// Initialize the heap to store the potential kth shortest path.

B = [];

for k from 1 to K:

// The spur node ranges from the first node to the next to last node in the shortest path.

for i from 0 to size(A[i]) − 1:

// Spur node is retrieved from the previous k-shortest path, k − 1.

spurNode = A[k-1].node(i);

// The sequence of nodes from the source to the spur node of the previous k-shortest path.

rootPath = A[k-1].nodes(0, i);

for each path p in A:

if rootPath == p.nodes(0, i):

// Remove the links that are part of the previous shortest paths which share the same root path.

remove p.edge(i, i) from Graph;

// Calculate the spur path from the spur node to the sink.

spurPath = Dijkstra(Graph, spurNode, sink);

// Entire path is made up of the root path and spur path.

totalPath = rootPath + spurPath;

// Add the potential k-shortest path to the heap.

B.append(totalPath);

// Add back the edges that were removed from the graph.

restore edges to Graph;

// Sort the potential k-shortest paths by cost.

B.sort();

// Add the lowest cost path becomes the k-shortest path.

A[k] = B[0];

return A;

主要的问题是我还不能为此编写正确的python脚本(删除边缘并将它们正确地放回原处),因此我只能像往常一样依靠Igraph来达到此目的：

def yenksp(graph,source,sink, k):

global distance

"""Determine the shortest path from the source to the sink."""

a = graph.get_shortest_paths(source, sink, weights=distance, mode=ALL, output="vpath")[0]

b = [] #Initialize the heap to store the potential kth shortest path

#for xk in range(1,k):

for xk in range(1,k+1):

#for i in range(0,len(a)-1):

for i in range(0,len(a)):

if i != len(a[:-1])-1:

spurnode = a[i]

rootpath = a[0:i]

#I should remove edges part of the previous shortest paths, but...:

for p in a:

if rootpath == p:

graph.delete_edges(i)

spurpath = graph.get_shortest_paths(spurnode, sink, weights=distance, mode=ALL, output="vpath")[0]

totalpath = rootpath + spurpath

b.append(totalpath)

# should restore the edges

# graph.add_edges([(0,i)])

graph.add_edges(i)

b.sort()

a[k] = b[0]

return a

这是一次非常糟糕的尝试,它只返回列表中的一个列表

我现在不太确定我在做什么,我已经非常渴望这个问题,在最后几天,我对此的观点已经改变了180度,甚至一次.

我只是尽力而为的菜鸟.请帮忙.也可以建议使用Networkx.

附言可能没有其他可行的解决方法,因为我们已经在这里进行了研究.我已经收到很多建议,而且我对社区有很多欠. DFS或BFS无法正常工作.图是巨大的.

编辑：我一直在纠正python脚本.简而言之,这个问题的目的是正确的脚本.

解决方法:

在Github,YenKSP上有一个Yen’s KSP的python实现.完全感谢作者,此处给出了算法的核心：

def ksp_yen(graph, node_start, node_end, max_k=2):

distances, previous = dijkstra(graph, node_start)

A = [{'cost': distances[node_end],

'path': path(previous, node_start, node_end)}]

B = []

if not A[0]['path']: return A

for k in range(1, max_k):

for i in range(0, len(A[-1]['path']) - 1):

node_spur = A[-1]['path'][i]

path_root = A[-1]['path'][:i+1]

edges_removed = []

for path_k in A:

curr_path = path_k['path']

if len(curr_path) > i and path_root == curr_path[:i+1]:

cost = graph.remove_edge(curr_path[i], curr_path[i+1])

if cost == -1:

continue

edges_removed.append([curr_path[i], curr_path[i+1], cost])

path_spur = dijkstra(graph, node_spur, node_end)

if path_spur['path']:

path_total = path_root[:-1] + path_spur['path']

dist_total = distances[node_spur] + path_spur['cost']

potential_k = {'cost': dist_total, 'path': path_total}

if not (potential_k in B):

B.append(potential_k)

for edge in edges_removed:

graph.add_edge(edge[0], edge[1], edge[2])

if len(B):

B = sorted(B, key=itemgetter('cost'))

A.append(B[0])

B.pop(0)

else:

break

return A

标签：igraph,graph,path,networkx,python