Find the minimum bottleneck path on the chart

Question

consider a complete graph with n vertices. Each vertex matters. the weight of the edge between the two vertices i and j is equal to the value [i] xor value [j].
the question is to find the path from vertex 1 to vertex n, where the maximum embedding of the edges in the path is minimal. I have already modified Dijkstra's algorithm and found the O (n ^ 2 log (n)) algorithm. can anyone help me find a more efficient algorithm?

Answer 1

The minimum bottleneck value cannot be less than the number determined by the most significant bit ( M ) of this value: value[1] XOR value[n] . If you find two nodes A and B , such that M and the higher bits of nodes 1 and A are equal, and M and the higher bits of nodes n and B are equal, with a minimum edge weight between A and B , the minimum bottleneck path will be 1-ABn (or it may be shorter if A = 1 and / or B = n).

To select an A/B pair with the minimum edge weight, build a binary trie for all node values ​​with higher order bits ( M and higher) matching node 1 . Then, for all node values ​​with higher order bits matching node n , try searching for these values ​​in this trie. If no exact match is found, select the deepest partial match.

The time complexity is O (n * M).