两个顶点通过一组给定的最短路径 [英] Minimum path between two vertices passing through a given set

问题描述

假设我有一个源节点的取值，目的节点的ð和一组 A 的中间节点 P1，P2，P3 ...... 在边加权无向图。我想找到顶点的的丕∈A 的是 减少DIST（S，PI）+ DIST（D，PI）的？此外，从整体路径的取值为D 应包含的只有一个从设置节点的。什么是一个高效的算法呢？我不想去与蛮力的方法。

Suppose I have a source node S, destination node D and a set A of intermediate nodes P1,P2, P3,… in an edge-weighted undirected graph. I want to find the vertex Pi ∈ A that minimizes dist(S,Pi)+dist(D,Pi)? In addition, the overall path from S to D should contain only one node from the set A. What is an efficient algorithm for this? I don't want to go with brute-force approach.

推荐答案

你说的蛮力是什么意思？

What do you mean by brute force?

如果您删除有关从集合A中只有一个节点比你可以进行如下的假设：

If you remove the assumption about "only one node from the set A" than you could proceed as follows:

• 找到所有皮从最短的路径（一个调用Dijkstra算法）
• 找到所有皮从D-最短路径（一次调用Dijkstra算法）
• 在遍历皮，然后选择一个最小化D（S，PI）+ D（D，PI）

复杂性：线性A的条款提出你的Dijkstra实施加复杂性（取决于所用的堆结构）

Complexity: linear in terms of A plus complexity of your Dijkstra implementation (depends on the heap structure used)

通过你的假设，我想你必须运行每个丕独立最短路径搜索

With your assumption, I suppose you have to run shortest path search from each Pi independently

• 对于每一个皮
  • 找到最短pathto S和D在grapg摹\自动{丕}（删除所有其他PJ的）
  • For each Pi
    • find shortest pathto S and D in the grapg G \ A u {Pi} (remove all other Pj's)

    现在的复杂性becoms一个时代的最短路径算法的复杂度（Dijkstra算法或其他）

    Now the complexity becoms A times the complexity of your shortest path algorithm (Dijkstra or other)

    以上两种方法相结合是创建一个理论图，这将对经过A点的，所以从实用的角度唯一路径，你会：

    Combination of two above approaches would be to create a "theoretical" graph, which would have only paths going through one point of A, so from practical point of view you would:

    • 找到所有丕假设你不跨越其他任何元素从最短的路径，则可以通过承担做到这一点，那小童有没有外的边缘。这样一来，Dijkstra算法将正确地识别距离从S到皮没有穿越任何其他PJ的
    • 找到从D-最短路径，所有PI（与上面相同）
    • 在遍历皮，然后选择一个最小化D（S，PI）+ D（D，PI）

    复杂性：线性所述的方面的迪杰斯特拉执行加复杂性（取决于所用的堆结构），因此它是一样的迪杰斯特拉（其具有至少读的所有顶点的complexit，所以线性在一个方面的复杂性是无关紧要的）。

    Complexity: linear in terms of A plus complexity of your Dijkstra implementation (depends on the heap structure used), so it is the same as the complexit of Dijkstra (which has to at least "read" all the vertices, so linear complexity in terms of A is irrelevant).

    这篇关于两个顶点通过一组给定的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！