经过深入研究并基于this,this和更多建议,我被建议在大型无向、循环、加权图中实现k短路径算法,以找到第一、第二、第三... k个最短路径。约2000个节点。
维基百科上的伪代码如下:
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)]) <- this is definitely not correct.
graph.add_edges(i)
b.sort()
a[k] = b[0]
return a
这只是一个很差的尝试,它只返回一个列表中的列表。
我已经不太确定我在做什么了,我已经非常绝望了,在过去的几天里,我的观点已经改变了180度,甚至有一次。我只是一个尽力而为的新手,请帮忙。还可以建议Networkx实现。
附言:很可能没有其他有效的方法,因为我们已经在这里进行了研究。我已经收到了很多建议,并且感谢社区。深度优先搜索(DFS)或广度优先搜索(BFS)都行不通。图形很大。
编辑:我一直在纠正Python脚本。简而言之,这个问题的目的是正确的脚本。