Influence of the link weight structure on the shortest path

The shortest path tree rooted at a source to all other nodes is investigated in a graph with polynomial link weights tunable by the power exponent alpha. By varying alpha, different types of shortest path trees, in short alpha trees, appear. Especially, the alpha --> 0 regime that corresponds to heavily fluctuating link weights possesses a peculiar type of tree. The most important properties of this alpha --> 0 tree are derived in the asymptotic limit for large N. The application of the theoretical insights to real networks (such as the Internet) are discussed: steering flow by adjusting link weights (traffic engineering), sensitivity of link weights and modeling of the network by alpha trees.