在圖中找到最小瓶頸路徑

Question

考慮我們有一個包含n個頂點的完整圖。每個頂點都有一個值。兩個頂點i和j之間的邊的權重等於值[i] xor值[j]。
問題是要找到從頂點1到頂點n的路徑，其中路徑邊緣的最大稱重是最小的。我已經修改了Dijkstra的算法，並找到了O（n^2 lg（n））的算法。有人可以幫助我找到更有效的算法嗎？

Answer 1

最小瓶頸值不能小於此值的最高有效位（M）確定的數量：value[1] XOR value[n]。如果發現兩個節點A和B，使得M和節點的較高位1和A相等以及等於是節點n和B的M和更高的位，以A和B，最小瓶頸路徑之間最小的邊的權重將是1-ABn（或者如果A = 1和/或B = n，則可能更短）。

要選擇A/B對以最小的邊的權重，構造一個二進制特里結構爲與節點重合1高階位（M和更高）的所有節點的值。然後，對於高位比特與節點n重合的所有節點值，嘗試在此特里搜索這些值。如果未找到完全匹配，請選擇最深部分匹配。

時間複雜度爲O（n * M）。