在区间图中找到两个节点之间的最有效路径

Question

我有区间数据：

A = (0,50)
B = (20,500)
C = (80,420)
....

并意识到此数据有一个关联图，the interval graph

我想找到从 A 到 G 的最有效路径（假设我知道所有正顶点权重，wa、wb、wc...）。我需要从 A 开始到 G，所以必须在这些点之间绑定最小生成树。我们应用程序中的限制之一是必须完全覆盖从 A 开始到 G 结束的区间（无间隙）。我正在查看 networkX's minspanning tree method，但不明白如何指定 A 和 G 必须是起点和终点。

想到的其他一些问题是：

既然这个问题是NP-hard的，那么如果节点数很高，我是否还要费心去寻找最小生成树呢？多少个节点会太多？
注意区间 F 有一个独特的区域。换句话说，要完全覆盖区间A-G，必须经过F。因此，我的最小生成树应该只连接A-F，而不是A-G。给定一个更大的图，是否有一种标准方法可以找到其间隔不包含唯一补丁的所有子图？换句话说，由于所有路径都必须通过 F 才能到达 G，因此 A-F 是感兴趣的最小生成路径，而不是 A-G。如何在不手动检查的情况下以这种方式缩小图表？
因为要从A-G走，所以我绝不会倒退，也不会走环路。例如，我永远不会去 A-B-A。生成树包含这个吗？这会使我的图表有向吗？考虑 C 点：可以从 C 到 D、E 或 F，但永远不会回到 A（对于我们的用例）。这对于图表的方向性意味着什么？

抱歉新手 Q，大部分内容都是新手。

Answer 1

如果您必须以高效的方式从 A 转到 G，那么您并不是在寻找最小生成树算法。一个简单的最短路径算法就足够了。您只需要调整图表以将权重放在边缘而不是节点中。但这只是将节点的权重设置为传入边缘的问题。

此外，最短路径和最小生成树问题都不是 NP 难问题。所有这些问题都有已知的多项式算法。特别地，最短路径可以用Dijkstra's algorithm (if your graph doesn't have negative edges, which seems to be true) and minimum spanning tree can be solved by Prim's or Kruskal's algorithm.

来求解

最后，根据定义，任何树都没有环。

Answer 2

正如另一个答案中提到的，Dijkstra 的算法是解决方案。没有提到的是如何在 networkx 中实现该解决方案。这里是。就这么简单：

import networkx as nx
my_graph = nx.Graph()
my_graph.add_edges_from([('A','B'),('B','C'),('A','C'),('C','D'),('A','D'),('C','E'),('D','E'),('D','F'),('F','G')]) 
#graph is now defined.

shortestpath = nx.dijkstra_path(my_graph, 'A', 'G') #optional weight argument here.
shortestpath
> ['A', 'D', 'F', 'G']

一般来说，有关如何在 networkx 中执行最短路径算法（及其许多变体）的更多文档是 here。

请注意，如果节点上有权重并且想要最小化路径中节点的总和，您要做的是在边上放置权重，以便 (u, v) 是 (w[u]+w[v])/2。

然后运行 nx.dijkstra_path 使用可选参数告诉 networkx 在哪里可以找到边的权重。整个路径的权重将等于中间权重的总和，加上末端节点值的一半。然后您可以校正末端节点权重。

在区间图中找到两个节点之间的最有效路径

Finding most efficient path between two nodes in an interval graph

algorithm

graph-theory

graph

dynamic-programming

networkx