  We study shortest paths and spanning trees of complex networks with random
edge weights. Edges which do not belong to the spanning tree are inactive in a
transport process within the network. The introduction of quenched disorder
modifies the spanning tree such that some edges are activated and the network
diameter is increased. With analytic random-walk mappings and numerical
analysis, we find that the spanning tree is unstable to the introduction of
disorder and displays a phase-transition-like behavior at zero disorder
strength $\epsilon=0$. In the infinite network-size limit ($N\to \infty$), we
obtain a continuous transition with the density of activated edges $\Phi$
growing like $\Phi \sim \epsilon^1$ and with the diameter-expansion coefficient
$\Upsilon$ growing like $\Upsilon\sim \epsilon^2$ in the regular network, and
first-order transitions with discontinuous jumps in $\Phi$ and $\Upsilon$ at
$\epsilon=0$ for the small-world (SW) network and the Barab\'asi-Albert
scale-free (SF) network. The asymptotic scaling behavior sets in when $N\gg
N_c$, where the crossover size scales as $N_c\sim \epsilon^{-2}$ for the
regular network, $N_c \sim \exp[\alpha \epsilon^{-2}]$ for the SW network, and
$N_c \sim \exp[\alpha |\ln \epsilon| \epsilon^{-2}]$ for the SF network. In a
transient regime with $N\ll N_c$, there is an infinite-order transition with
$\Phi\sim \Upsilon \sim \exp[-\alpha / (\epsilon^2 \ln N)]$ for the SW network
and $\sim \exp[ -\alpha / (\epsilon^2 \ln N/\ln\ln N)]$ for the SF network. It
shows that the transport pattern is practically most stable in the SF network.
