在图中寻找最小瓶颈路径

Question

在图中寻找最小瓶颈路径

4

考虑我们有一个有n个顶点的完全图。每个顶点都有一个值。两个顶点i和j之间的边的权重等于value[i]异或value[j]。
问题是找到从顶点1到顶点n的路径，使路径中边的最大权重最小。我已经修改了Dijkstra算法，并找到了一个O(n ^ 2 lg(n))的算法。有人能帮我找到更有效的算法吗？

- Stranger

你是指 O(n * log n) 吗？还是 O(n^(log n))？ - templatetypedef

2

@templatetypedef 我认为他的意思是O(n * n * logn)？ - zw324

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

最小瓶颈值不能小于由该值的最高有效位（M）确定的数字：value[1] XOR value[n]。如果你找到两个节点A和B，使得节点1和A的M及更高位相等，并且n和B的M及更高位也相等，在A和B之间具有最小边权，则最小瓶颈路径为1-A-B-n（如果A=1和/或B=n，则可能更短）。

要选择具有最小边权的A/B对，请为所有节点值构建二进制trie，其中高位（M及更高位）与节点1重合。然后，对于所有高位与节点n重合的节点值，请尝试在此trie中搜索这些值。如果没有找到精确匹配，则选择最深的部分匹配。

时间复杂度为O(n * M)。