Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci In a series graph, each edge $e_i$ exists with probability $p_i$. And if you want to examine the existence of edge $e_i$, it will cost you $c_i$. I want to test the connectivity between source $s$ and destination $d$ with the minimum expexted cost.

I have figured out that the expected cost can be caculated below if the edge detection sequence is $e_1, e_2, \cdots e_n$:

$$E(cost) = c_1 + p_1 * (c_2 + p_2 * (c_3 + p_3 * (\cdots (c_{n-1} + p_{n-1} * c_n)\cdots))))$$

So is there a stretegy or algorithm to find out the minimum expected cost and the edge detection sequence?
Suppose that you test the edges in order. The expected cost is thus
$$
\sum_{i=1}^n c_i \prod_{j=1}^{i-1} p_j.
$$
Now suppose that we switch the order of $k$ and $k+1$. The two relevant terms are
$$
c_k \prod_{j=1}^{k-1} p_j + c_{k+1} \prod_{j=1}^k p_j.
$$
After switching $k$ and $k+1$, these two terms become
$$
c_{k+1} \prod_{j=1}^{k-1} p_j + c_k p_{k+1} \prod_{j=1}^{k-1} p_j.
$$
Dividing by $\prod_{j=1}^{k-1} p_j$, these two expressions become
$$
c_k + p_k c_{k+1} \\
c_{k+1} + p_{k+1} c_k
$$
The switch leads to an improvement if
$$
c_k + p_k c_{k+1} &gt; c_{k+1} + p_{k+1} c_k \\ \Longleftrightarrow \\
c_k (1-p_{k+1}) &gt; (1-p_k) c_{k+1} \\ \Longleftrightarrow \\
\frac{c_k}{1-p_k} &gt; \frac{c_{k+1}}{1-p_{k+1}}.
$$
This suggests testing the edges in increasing order of
$$
\frac{c_i}{1-p_i}.
$$