我正在尝试根据https://en.wikipedia.org/wiki/Yen%27s_algorithm上的伪代码实现Yen的K最短路径算法。以下是代码。
显然,算法错过了一些更短的路径。而且结果包含有环的路径。我只想要没有这种情况的路径。
另外,在其他情况下,结果的顺序是错误的,一些较长的路径出现在其他更短的路径之前。在 KSP 问题中,结果的顺序显然很重要,因为如果我停留在某个 k 上,我希望能确定我没有错过更短的路径。
我愿意尝试其他能够正确有效地解决无向非加权图上 KSP 问题且没有环的算法。
请帮忙。
import numpy as np
import networkx as nx
edge_list = [[0, 1], [0, 2], [0, 7], [1, 2], [1, 9], [2, 5], [2, 7], [2, 9], [3, 4], [3, 5], [3, 6], [3, 8], [4, 5], [4, 6], [4, 7], [4, 8], [5, 6], [5, 7], [5, 8], [6, 8], [7, 8]]
graph = nx.Graph()
graph.add_edges_from(edge_list)
nx.draw(graph, with_labels = True)
source_node = 8
destination_node = 9
def yen_ksp(graph, source, sink, K):
A, B = [], []
A.append(nx.shortest_path(graph, source=source, target=sink))
for k in range(1, 1+K):
for i in range(len(A[k - 1]) - 1):
spurNode = A[k-1][i]
rootPath = A[k-1][0:i+1]
removed_edges, removed_nodes = [], []
for p in A:
if rootPath == p[0:i+1] and p[i:i+2] not in removed_edges:
removed_edges.append(p[i:i+2])
for edge in removed_edges:
graph.remove_edge(edge[0], edge[1])
try:
spurPath = nx.shortest_path(graph, source=spurNode, target=sink)
except:
for edge in removed_edges:
graph.add_edge(edge[0], edge[1])
continue
totalPath = rootPath + spurPath[1:]
B.append(totalPath)
for edge in removed_edges:
graph.add_edge(edge[0], edge[1])
if B == []:
# This handles the case of there being no spur paths, or no spur paths left.
# This could happen if the spur paths have already been exhausted (added to A),
# or there are no spur paths at all - such as when both the source and sink vertices
# lie along a "dead end".
break
B.sort()
A.append(B[-1])
B.pop(-1)
return A
print(yen_ksp(graph.copy(), source_node, destination_node, 10))
这应该是从上面的代码生成的无向、无权图。
这是代码的输出结果。
[[8, 5, 2, 9],
[8, 7, 2, 9],
[8, 7, 2, 1, 9],
[8, 7, 2, 1, 2, 9],
[8, 7, 2, 1, 2, 1, 9],
[8, 7, 2, 1, 2, 1, 2, 9],
[8, 7, 2, 1, 2, 1, 2, 1, 9],
[8, 7, 2, 1, 2, 1, 2, 1, 2, 9],
[8, 7, 2, 1, 2, 1, 2, 1, 2, 1, 9],
[8, 7, 2, 1, 2, 1, 2, 1, 2, 1, 2, 9],
[8, 7, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 9]]
显然,算法错过了一些更短的路径。而且结果包含有环的路径。我只想要没有这种情况的路径。
另外,在其他情况下,结果的顺序是错误的,一些较长的路径出现在其他更短的路径之前。在 KSP 问题中,结果的顺序显然很重要,因为如果我停留在某个 k 上,我希望能确定我没有错过更短的路径。
我愿意尝试其他能够正确有效地解决无向非加权图上 KSP 问题且没有环的算法。
请帮忙。