How we can prove that shortest path between two nodes is unique if all
the weights are unique power of 2.
Clarification of Question bynivis-ga
I need to Know that how the shortest path is unique if weights are
power of 2. NO retracing allowed. edge would be consider once.
Request for Question Clarification bymathtalk-ga
You need more than simply the edge weights being a power of two. They
need to be, as you specified originally in the problem, _unique_
powers of two.
That is, the weights on two different edges are distinct powers of two.
Maybe it helps to see the point of this if you look at a simple
example. Draw a square, and set the weight of each vertex to be the
same power of two, e.g. 1 to keep things simple.
What is the "shortest" from one corner to the opposite corner? You
have two edges to transverse, for a minimum "distance" of 2, but the
path could go around the square either clockwise or counterclockwise.
Thus the shortest path is _not_ unique here.
Now change the four edge weights in this problem so they are all
different powers of two. Since the powers are unequal, when you add
up a sequence of them, what is the relationship between the edges
travelled and the binary representation of the sum of weights?