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?


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.