Given a directed weighted graph G = (V, E) with every edge e has weight w(e) > 1. Assume G

contains a node s that can reach all other nodes.

Suppose we square the weights of the edges in G. In other words, we have the same graph G

except every edge e has a squared weight w1(e) = w(e)2. The shortest path tree now might

change compared to what you have before. If we change the tree by squaring the weights

again, until two successive shortest path trees are identical. Argue that further squaring will

not change the shortest path tree. Thus, these shortest paths now can be defined with no

reference to the actual weights. i.e., given two paths instead of evaluating whether path p1

is shorter than path p2 can be determined just by comparing weights, without having the

operation of addition of weights. Describe this characterization of the way of comparing the

length of paths.

Example: Suppose when we started there are just two paths, each of two edges, from s to

some v, One path has two edges of weights 5 and 5 and the other 7 and 2. At the beginning,

the 7,1 path is the shortest because its length is 9 and the other is 10, but after one squaring

we will get 25, 25, and 49, 4, respectively. Now the shortest path is the previous 5,5! Why

this happened? The most weighty edge between the two paths is 7, and squaring enough

will get it to dominate. If the two paths were tied with respect to the most weighty, then the

second most weighty will break the tie, etc.