algorithm - 在图中找到一个节点，使两个其他节点之间的距离最小

Question

我有一个有向加权图 G，有 V 个顶点和 E 个边。给定图中的两个节点，假设 A 和 B，并给定边 A-B 的权重，表示为 w(A, B)，我需要找到一个节点 C，以便 max(w(A, C), w (B, C)) 在所有可能性中是最小的。我所说的可能性是指 C 可以采用的所有值。我不知道是否完全清楚，如果不是，我会尝试更精确。

Answer 1

如果 w(A, C) 你真的只是指边的权重，然后依次检查直接连接到 A 的所有节点，总成本最差的是图的大小，大约与你可以期望，假设你总是需要阅读图表。

如果 w(A, C) 是指从 A 到 C 的最低成本路径的成本，请注意大多数寻路算法，例如 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ，实际上是计算从 A 到每个其他节点的最小成本路径的成本。如果您既有从 A 到每个节点的成本，也有从每个节点到 B 的成本，则可以通过依次查看每个节点来解决您的问题。

因此，运行一次计算出从 A 到每个其他节点的成本，然后反转节点中的边，再运行一次计算出从 B 到反转图中每个其他节点的成本最低路径。然后对于每个节点，您有最低成本 w(A, C) 和最低成本 w(C, B) 的成本，因此您可以依次检查每个节点，看看哪个是最好的。

如果您的图形包含循环，那么您需要像 http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm 这样的东西.如果它有负循环，你就会有问题。