Shortest Path

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?

regards, mathtalk-ga

Leave a Reply

Your email address will not be published. Required fields are marked *