algorithm - 通过给定集合的两个顶点之间的最小路径

Question

假设我有一个源节点S、目标节点D 和一组A 中间节点P1、P2、P3 ,… 在边加权无向图中。我想找到 Pi ∈ A 最小化 dist(S,Pi)+dist(D,Pi)?此外，从S 到D 的整个路径应该只包含集合A 中的一个节点。什么是有效的算法？我不想采用蛮力方法。

Answer 1

暴力是什么意思？

没有假设

如果您删除关于“集合 A 中只有一个节点”的假设，那么您可以按如下方式进行:

• 找到从 S 到所有 Pi 的最短路径(一次调用 Dijkstra 算法)
• 找到从 D 到所有 Pi 的最短路径(调用 Dijkstra 算法一次)
• 遍历 Pi 并选择最小化 d(S,Pi)+d(D,Pi) 的那个

复杂性:根据 A 加上 Dijkstra 实现的复杂性呈线性关系(取决于所使用的堆结构)

假设

根据您的假设，我想您必须独立地从每个 Pi 运行最短路径搜索

• 对于每个 Pi
  • 在图形 G\A u {Pi} 中找到到 S 和 D 的最短路径(删除所有其他 Pj)
• 遍历 Pi 并选择最小化 d(S,Pi)+d(D,Pi) 的那个

现在复杂度变成了最短路径算法(Dijkstra 或其他算法)的 A 倍

假设 - 似乎是最优的

上述两种方法的组合将创建一个“理论”图，该图将只有通过 A 点的路径，因此从实际的角度来看，您将:

• 假设您不穿过 A 的任何其他元素，找到从 S 到所有 Pi 的最短路径，您可以通过假设 Pis 没有“外”边来做到这一点。这样，dijkstra 算法将正确识别从 S 到 Pi 的距离，而不会跨越任何其他 Pj
• 寻找从D到所有Pi的最短路径(同上)
• 遍历 Pi 并选择最小化 d(S,Pi)+d(D,Pi) 的那个

复杂性:根据 A 加上您的 Dijkstra 实现的复杂性(取决于使用的堆结构)是线性的，因此它与 Dijkstra 的复杂性相同(它必须至少“读取”所有顶点，因此是线性的A 的复杂性无关紧要)。