考虑我们有一个包含 n 个顶点的完整图。每个顶点都有一个值。两个顶点 i 和 j 之间的边的权重等于 value[i] xor value[j]。
问题是找到从顶点 1 到顶点 n 的路径，该路径中边的最大权重最小。我已经修改了 Dijkstra 的算法，发现了一个 O(n ^ 2 lg(n)) 的算法。有人可以帮我找到更有效的算法吗？
问问题
2070 次
1 回答
1
最小瓶颈值不能小M于此值的最高有效位 ( ) 确定的数字：value[1] XOR value[n]。如果你找到两个节点A和B，这样M和 的更高位的节点1和A相等，以及M和 的更高位的节点n和，在和B之间具有最小的边权重，最小瓶颈路径将是 1-ABn （或者它可能是如果 A=1 和/或 B=n 则更短）。AB
要选择具有最小边权重的对，请为所有具有与 node 重合的A/B高位（和更高位）的节点值构造一个二叉树。然后对于所有高位与 node 重合的节点值，尝试在这个 trie 中搜索这些值。如果未找到完全匹配，则选择最深的部分匹配。M1n
时间复杂度为 O(n * M)。
于 2013-06-29T10:13:21.073 回答