How we can prove that shortest path between two nodes is unique if all
the weights  are unique power of 2.

---

Clarification of Question by nivis-ga on 18 Nov 2003 18:06 PST

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 by mathtalk-ga on 19 Nov 2003 18:50 PST

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?

regards, mathtalk-ga

Ummm... two different paths would have distinct sums?  The bits in a
weighted sum would uniquely identify the edges taken in a simple path
(no retracing of edges allowed).  You may need to say a few words
about why a shortest path will always be simple.

-- mathtalk-ga