3
$\begingroup$

Suppose we have a complete graph $G$ with $n$ vertices. Every edge $e_i$ in the graph has a weight $w_i$ and is assigned a probability $p_i$ which indicates the probability with which the edge $e_i$ exists. Also assume that $G$ is acyclic, that is the edges are directed as $(v_i \rightarrow v_j)$ for $j > i$.

Now my question is, how do I go about finding the length of the expected shortest path? If I understand this correctly, there are $2^{n-2}$ possible intermediate vertices and hence that many paths. We can compute the probabilities with which each of these paths exist in the graph. But how do I use it to compute the expected length? (It will still be exponential though).

Is there a better way of doing this?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.