我有一个有向加权图 G，有 V 个顶点和 E 个边。给定图中的两个节点，假设 A 和 B，并给定一条边 AB 的权重，表示为 w(A, B)，我需要找到一个节点 C 使得 max(w(A, C), w (B, C)) 在所有可能性中是最小的。我所说的可能性是指 C 可以采用的所有值。我不知道它是否完全清楚，如果不是，我会尝试更准确。
问问题
1498 次
2 回答
2
如果 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的东西。如果它有负循环，你就会遇到问题。
于 2012-11-13T04:56:45.397 回答
0
不是很清楚你问什么，但这里是加权距离的一种方法：将其视为 R^n 中的距离问题，其中在任何维度上到 C 的实际直线距离乘以路径的该维度的权重以获得加权距离。使整个表达式成为加权距离的总和，并使用二阶导数测试来最大化该表达式。
干杯，安德鲁
于 2012-11-13T04:52:32.210 回答