algorithm - 最小化和同时最小化差异

Question

我想找到同时满足以下两个条件的节点(比如索引 i):

1. 最小化从节点 A 到节点 i 的距离总和，比如说 d(A,i)，从节点i 到节点 B，比如 d(i,B)，即 min d(A,i)+d(i ,B)

2. 最小化这些距离之间的差异，即 min |d(A,i)-d(i,B)|。

可能这是一个众所周知的问题，但我找不到任何开发合适算法的引用资料。

Answer 1

计算 A 到所有其他节点的距离，然后计算 B 到逆图中所有其他节点的距离(如果你的图不是有向的，那么它在原始图中)。

您可以运行 bellman ford O(VE) 或 Dijkstra (ElogV)。

然后遍历每个节点，计算出 d(A,i) 和 d(B,i)，因此选择满足您标准的节点，听起来您应该更喜欢 min d(A,i)+ d(i,B) 大于 min|d(A,i) - d(i,B)|。在任何情况下，您都将拥有所有值，因此您只需要选择您想要的值。这将是 O(V)。

假设您使用 Dijkstra 来解决，那么总体而言，您的解决方案将是 O(ElogV)。