How to find probability of path in a directed graph?

I have a directed weighted graph G=(V,E).

In this graph the weight of edge(v[i],v[j]) is the count of transition between v[i] and v[j].

I am trying to determine the best way to accomplish task: how to find the probability P of path from node A to node B

All weights are positive integers.

For example,

weight(A,B)=count of transition from A to B
weight(B,C)=count of transition from B to C
weight(B,D)=count of transition from B to D
weight(D,C)=count of transition from D to C

And we have several paths:


So, how to calculate probability P of these paths and choose the best one?


It can be solved by reducing the problem to shortest path problem, assuming we are indeed discussing probabilities (that means, each weight is in range [0,1]).

Let the graph be G=(V,E), and the probability between two vertices denoted as w(u,v).

Define: w'(u,v) = -log(w(u,v))

The shortest path from some node s to some node t is then the shortest path in the graph when using w' as weight function. You can find the shortest path using Dijkstra's algorithm or Bellman-Ford algorithm


For a path v1->v2->...->vn, its probability is w(v1,v2) * w(v2,v3) * ... * w(vn-1,vn).

When using w' as the weight, the cost of this path when using any shortest path algorithm is:

d(v1,vn) = w'(v1,v2) + w'(v2,v3) + ... + w'(vn-1,vn) = 
d(v1,vn) = -log(w(v1,v2)) + -log(w(v2,v3) + ... + -log(w(vn-1,vn)) = 
d(v1,vn) = -1* [ log(w(v1,v2)) + log(w(v2,v3)) + ... + log(w(vn-1,vn)) =
d(v1,vn) = -1* log(w(v1,v2) * w(v2,v3) * ... * w(vn-1,vn)) 

This obviously applies also for the minimal path found from s to t.
This means that this path have minimal value of:

s(s,t) = -1* log(w(s,v2) * w(v2,v3) * ... * w(vn-1,t)) 

And since log is monotonic function, it is also minimal value of -1 * w(s,v2) * w(v2,v3) * ... * w(vn-1,t), which is the maximal value of w(s,v2) * w(v2,v3) * ... * w(vn-1,t), and that's exactly the probability.


 ? path between two disjoint sets (path algorithm)
 ? How to convert List of Edges to Adjacency Matrix in C++ with the number of edges connected to a vertex instead of ones?
 ? Reasonable type for Directed graph in Ocaml
 ? How to select k nodes in a fully connected graph with max separation between any pair of nodes?
 ? How to increase the speed of calculation the number of specific leaves in tree
 ? Modified Depth-First-Search Python
 ? Efficient way to eliminate isolated vertices and reorder the vertices of resulting graph
 ? Find the Diameter of data in a text file using R
 ? Finding no. of edges in a graph
 ? Merge relationship does not always work (delay)