Networkx最短树算法
Networkx shortest tree algorithm
我有一个带有一组节点和加权边的无向加权图 G。
我想知道是否有在 networkx 中实现的方法来在图中找到 给定节点 之间的最小生成树（例如 nx.steiner_tree(G, [ 'Berlin', 'Kiel', 'Munster', 'Nurnberg'])) (貌似有none?)
我没有 post 图片的声望点。相似图像的 link 可以是：
Map
(A3, C1, C5, E4)
我在想什么：
- 检查所有目标节点之间的 dijkstras 最短路径；
- 将所有节点（中间和目的地）和边放入新图 V；
- 计算 V 上的 mst（通过打破最长边来移除循环）；
也许有更好的方法（正确性和计算方面）？因为这种方法对三个目标节点的效果很差，而对更多节点的效果会更好。
P.S。我的图形是平面的（它可以画在纸上，这样边缘就不会相交）。所以也许某种 spring/force（比如在 d3 可视化中）算法会有所帮助？
据我了解你的问题，你正在尝试找到包含一组节点的最低权重连接组件。这就是 Steiner tree in graphs 问题。它是 NP 完全的。您最好根据您正在研究的具体案例采取某种启发式方法。
对于两个节点，执行此操作的方法是 Dijkstra 算法 - 如果围绕两个节点展开直到两个壳相交，则速度最快。对于三个节点，我怀疑围绕每个节点展开的 Dijkstra 算法的一个版本会产生一些好的结果，但我不知道如何确保你得到最好的结果。
我为此找到了 another question，它有几个不错的答案（发布的问题有一个未加权的图表，所以它是不同的，但答案中给出的算法适用于加权）。除了公认的答案之外，还有一些不错的答案。
在 networkx 中有一个标准的 Kruskal 算法，它使用无向加权图作为输入来实现。该函数称为“minimum_spanning_tree”
我建议你构建一个包含你需要的节点的子图，然后让 Kruskal 算法运行在它上面。
import nertworkx as nx
H=G.subgraph(['Berlin','Kiel', 'Konstanz'])
MST=nx.minimum_spanning_tree(H)
正如已经指出的，这是图形中的斯坦纳树问题。
networkx中有Steiner树算法：
但是，它只能给你一个近似解，而且速度也很慢。对于 state-of-the-art 解算器，请参阅下面的“外部链接”部分：
我有一个带有一组节点和加权边的无向加权图 G。
我想知道是否有在 networkx 中实现的方法来在图中找到 给定节点 之间的最小生成树（例如 nx.steiner_tree(G, [ 'Berlin', 'Kiel', 'Munster', 'Nurnberg'])) (貌似有none?)
我没有 post 图片的声望点。相似图像的 link 可以是： Map (A3, C1, C5, E4)
我在想什么：
- 检查所有目标节点之间的 dijkstras 最短路径；
- 将所有节点（中间和目的地）和边放入新图 V；
- 计算 V 上的 mst（通过打破最长边来移除循环）；
也许有更好的方法（正确性和计算方面）？因为这种方法对三个目标节点的效果很差，而对更多节点的效果会更好。
P.S。我的图形是平面的（它可以画在纸上，这样边缘就不会相交）。所以也许某种 spring/force（比如在 d3 可视化中）算法会有所帮助？
据我了解你的问题，你正在尝试找到包含一组节点的最低权重连接组件。这就是 Steiner tree in graphs 问题。它是 NP 完全的。您最好根据您正在研究的具体案例采取某种启发式方法。
对于两个节点，执行此操作的方法是 Dijkstra 算法 - 如果围绕两个节点展开直到两个壳相交，则速度最快。对于三个节点，我怀疑围绕每个节点展开的 Dijkstra 算法的一个版本会产生一些好的结果，但我不知道如何确保你得到最好的结果。
我为此找到了 another question，它有几个不错的答案（发布的问题有一个未加权的图表，所以它是不同的，但答案中给出的算法适用于加权）。除了公认的答案之外，还有一些不错的答案。
在 networkx 中有一个标准的 Kruskal 算法，它使用无向加权图作为输入来实现。该函数称为“minimum_spanning_tree”
我建议你构建一个包含你需要的节点的子图，然后让 Kruskal 算法运行在它上面。
import nertworkx as nx
H=G.subgraph(['Berlin','Kiel', 'Konstanz'])
MST=nx.minimum_spanning_tree(H)
正如已经指出的，这是图形中的斯坦纳树问题。 networkx中有Steiner树算法：
但是，它只能给你一个近似解，而且速度也很慢。对于 state-of-the-art 解算器，请参阅下面的“外部链接”部分：