Given a weighted directed graph $G=(V,E, w)$, suppose we generate a new graph $G'=(V,E,w')$ with the same vertices and edges, but now letting the weight of edge $(i,j)$ be
an exponential random variable with mean $w\_{ij}$. My question is: what is the
expected diameter of $G'$?


Why I'm interested in this: I was intrigued by the observation that the expected diameter of $G'$ can be
quite different from the diameter of $G$. Indeed, consider the following example: define $G$ by taking the complete graph $K\_{n+1}$, picking an arbitrary vertex $a$, and assigning weight $n$ to any edge incident on $a$, and weight $1$ to 
every other edge. Then, the diameter of $G$ is $n$. On the other hand, the expected diameter
of $G'$ is O(1) since we can expect one of the edges incident on $a$ to have small weight.



diameter of a graph with random edge weights
For the special case of the complete graph $K\_n$ which you mention in your post, Svante Janson answered your question in [this paper](http://portal.acm.org/citation.cfm?id=971602); the answer is that the weighted diameter grows like $3 \log n$ in probability. 


There is also some very nice [work by Bhamidi et. al](http://www.win.tue.nl/~rhofstad/ERRG_fin.pdf) on this question when the underlying graph is the giant component of Erdos--Renyi random graph $G\_{n,c/n}$ with $c>1$ fixed, although they only prove lower bounds. [Amini et. al.](http://www.di.ens.fr/~amini/Publication/Flooding.pdf) (link is to a PDF) have found the asymptotics of the weighted diameter for random graphs with a given degree sequence, under some conditions, for degree sequences which in particular result in graphs which are with high probability connected. [Ding et.al.](http://arxiv.org/abs/0906.1840) (Theorems 3.7 and 3.8 of the linked paper) prove quite refined estimates, and tail bounds, for the weighted diameter of random $d$-regular graphs, for $d \geq 3$. (Since random regular graphs are a special case of random graphs with a given degree sequence, the results of Amini et. al. and Ding et.al. have some overlap). 


There is also related work, on the *hopcount* of randomly weighted graphs. The hopcount is what you get if you count the number of edges on the smallest-weight path. The primary interest of Bhamidi et. al. in fact seems to be hopcounts rather than weighted path lengths. 


