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

Question

假设我在边缘加权无向图中具有源节点S,目的节点D和中间节点P1,P2,P3 ......的集合A. 我想找到顶点丕∈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
  • 在Grapg G\A u {Pi}找到S和D的最短路径(删除所有其他Pj)
• 通过Pi迭代并选择最小化d(S,Pi)+ d(D,Pi)的那个

现在复杂性是你最短路径算法(Dijkstra或其他)的复杂性的一倍

假设 - 似乎是最优的

上述两种方法的组合将是创建一个"理论"图形,其中只有路径通过A的一个点,因此从实际角度来看,您将:

• 找到从S到所有Pi的最短路径,假设你没有穿过A的任何其他元素,你可以通过假设Pis'没有"外"边缘来做到这一点.这样,dijkstra算法将正确识别从S到Pi的距离,而不会穿过任何其他Pj
• 找到从D到所有Pi的最短路径(与上面相同)
• 通过Pi迭代并选择最小化d(S,Pi)+ d(D,Pi)的那个

复杂性:A的线性加上Dijkstra实现的复杂性(取决于所使用的堆结构),因此它与Dijkstra的复杂性相同(它必须至少"读取"所有顶点,因此线性复杂度就术语而言A无关紧要).