Given a directed acyclic graph G=(V,E). For every node u and every directed edge (u, v), we are also given the probability that the system will go next to vertex v if it is in state u. The outgoing edges e needs to sum up to 1 (100%). If u is the final state (a sink), the vertex has no outgoing edges. The random decisions at different nodes u are assumed to be mutually independent.

There's exactly one source s and one sink t. Hence the possible behaviors of the system are exactly all directed st paths. This also defines a probability space whose elementary events are all these paths. Down below is an example of a DAG.

If we assign an individual time t_n to each vertex v, could you give me an algorithm/solution that computes the expected total duration of the traversed (random) path?

50%. 100% 50% 100% t 70% 200% 120% 30% % S 1007 100%