- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试基于 https://en.wikipedia.org/wiki/Yen%27s_algorithm 中的伪代码实现 Yen 的 K 最短路径算法。这是代码。
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 问题的算法持开放态度。
请帮忙。
最佳答案
Networkx 提供了一个函数,用于生成图中从源到目标的所有简单路径的列表,从最短的路径开始:shortest_simple_paths
。此过程完全基于 Yen 的算法,您可以在文档中阅读。
使用非常简单:
paths = list(nx.shortest_simple_paths(graph, source_node, target_node))
如果您只想要前 K 个最短路径,您可以使用 islice
:
from itertools import islice
paths = list(islice(nx.shortest_simple_paths(graph, source_node, target_node), K))
示例:
from itertools import islice
K = 10
source_node = 8
target_node = 9
graph = nx.Graph()
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.add_edges_from(edge_list)
for path in islice(nx.shortest_simple_paths(graph, source_node, target_node), K):
print(path)
输出:
[8, 5, 2, 9]
[8, 7, 2, 9]
[8, 5, 7, 2, 9]
[8, 5, 2, 1, 9]
[8, 3, 5, 2, 9]
[8, 7, 0, 1, 9]
[8, 7, 2, 1, 9]
[8, 4, 5, 2, 9]
[8, 7, 5, 2, 9]
[8, 7, 0, 2, 9]
如果您想了解 shortest_simple_path
是如何实现的,您可以查看其 source code : 写得很好,很容易理解!
关于algorithm - Yen 的 K 最短路径给出错误结果 (Python),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59056173/
我正在尝试基于 https://en.wikipedia.org/wiki/Yen%27s_algorithm 中的伪代码实现 Yen 的 K 最短路径算法。这是代码。 import numpy as
我偶然发现了著名的 Yen 对 Bellman-Ford 算法的优化,我最初是从 Wikipedia 得到的。 , 然后我在练习部分的几本教科书中发现了相同的改进(例如,这是 Cormen 中的问题
Bellman-Ford 算法对于解决单源最短路径问题很有用,并且具有独特且有趣的属性,即在第 k 次迭代时每个顶点的 k 跳最优性,这是我的应用程序所必需的。 (基本上,我想要一对顶点之间最多 k
经过深入研究并基于this , this还有很多建议我实现 k 最短路径算法,以便在大型无向循环加权图中找到第一、第二、第三……第 k 条最短路径。大约2000个节点。 Wikipedia 上的伪代码
我正在尝试在 python 中实现 Yen 提出的 Bellman-Ford 算法的优化,以及 Bannister & Eppstein 提出的随机加速。 我正在关注 Bannister 和 Epps
运行以下代码似乎生成了错误的值: byte[] data = "\u00a5".getBytes("Shift_JIS"); 它产生 [ -4, -4 ],但我期望 [ 0x5c ] 我尝试了各种替代
我已经根据维基百科上的伪代码和 GitHub 上的一些开源代码(https://gist.github.com/ALenfant/5491853 和 https://github.com/Pent00
我是一名优秀的程序员,十分优秀!