寻找两个节点之间的最有效的路径在一个区间图 [英] Finding most efficient path between two nodes in an interval graph
问题描述
我有时间的数据：
A = (0,50)
B = (20,500)
C = (80,420)
....
和意识到，有一个与此数据的关联图，区间图表
And realized that there's an associated graph with this data, the interval graph
我想找到最有效的路径从A到G（假设我知道所有的积极顶点权重，WA，WB，WC ......的）。我要开始在A和去G，所以最小生成树必须在这些点之间的约束。一个在我们的应用程序的限制是处开始和结束的时间间隔于G1必须全额（无间隙）被覆盖。我在看<一href="http://networkx.github.io/documentation/development/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html#networkx.algorithms.mst.minimum_spanning_tree"相对=nofollow> networkX的minspanning树法，不明白如何指定A和G必须是起点和终点。
I'd like to find the most efficient path to go from A to G (assume I know all of the positive vertex weights, wa, wb, wc...). I need to start at A and go to G, so the minimum spanning tree must be bound between these points. One of the constraints in our application is that the interval starting at A and ending at G must be covered in full (no gaps). I'm looking at networkX's minspanning tree method, and don't understand how to specify that A and G must be the start and endpoints.
这是我想到的一些其他问题是：
Some other questions that come to mind are:
-
由于这个问题是NP难的，我也懒得找一个最小生成树，如果节点的数量是高呢？多少个节点是太多？
Since this problem is NP-hard, should I even bother looking for a min-spanning tree if the number of nodes is high? How many nodes would be too many?
请注意，间隔F有一个独特的区域。换句话说，完全覆盖区间AG，一是要经过F.因此，我最小生成树或许应该只连接自动对焦，而不是公司。有没有一种标准的方式，赋予了更大的图形，找到所有的间隔不含有独特的补丁子图？换句话说，由于所有路径具有传递至F到达G，AF是最小生成树路径的兴趣，而不是AG。一个人如何以这样的方式减少，而不需要手动检查它的曲线
Notice that interval F has a unique region. In other words, to completely cover the interval A-G, one HAS to go through F. Therefore, my minimum spanning tree probably should only connect A-F, not A-G. Is there a standard way, given a larger graph, to find all of the subgraphs whose intervals contain no unique patches? In other words, since all paths have to pass through F to get to G, A-F is the min spanning path of interest, not A-G. How does one reduce a graph in such a way without inspecting it manually?
Becasue我从公司走，我绝不会倒退或采取循环路径。比如，我从来没有去A-B-A。不要生成树结合呢？而这是否让我的图形指示？考虑点C：从C人们可以去D，E或F，但从来没有回A（为我所用的情况下）。这是什么意思在考虑到图形的方向性？
Becasue I have to go from A-G, I would never go backwards or take a cyclic path. For example, I'd never go A-B-A. Do spanning trees incorporate this? And does this make my graph directed? Consider point C: from C one could go to D, E, or F, but never back to A (for our use case). What does this mean in regard to directionality of the graph?
对不起新手Q记者，新中的大部分。
Sorry for novice Q's, new to most of this.
推荐答案
如果你必须从A至G的一种有效的方式，你是不是在找一个最小生成树算法。一个简单的最短路径算法就足够了。你必须去适应你绘制把权重的边缘，而不是节点。但它的节点的权重设置为来电边缘的只是一个问题。
If you must go from A to G in an efficient way, you aren't looking for a minimum spanning tree algorithm. A simple shortest path algorithm is enough. You just have to adapt you graph to put the weights in the edges instead of the nodes. But it's just a matter of setting the node's weight to the incoming edge.
另外，无论是最短路径和最小生成树问题不是NP难。有公知的多项式算法的所有这些问题。在特殊的，最短路径可以通过 Dijkstra算法（如果你的图没有消极的边缘，这似乎是真实的）和最小生成树可以通过普里姆的解决或 Kruskal算法。
Also, both shortest path and minimum spanning tree problems aren't NP-hard. There are known polynomial algorithms for all these problems. In special, shortest path can be solved by 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.
最后，任何树，顾名思义没有循环。
And finally, any tree, by definition doesn't have cycles.
这篇关于寻找两个节点之间的最有效的路径在一个区间图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
