如何在有向图中找到路径的概率？

Question

我有一个有向加权图G=(V,E)。

在这个图中，edge(v[i],v[j]) 的权重是 v[i] 和 v[j] 之间的转换计数。

我正在尝试确定完成任务的最佳方法：如何找到从节点 A 到节点 B 的路径的概率 P

所有权重均为正整数。

例如，

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

我们有几条路径：

A->B->C 
A->B->D->C

那么，如何计算这些路径的概率P，并选择最佳路径呢？

Answer 1

可以通过将问题减少到shortest path problem来解决，假设我们确实在讨论概率（也就是说，每个权重都在[0,1]范围内）。

设图为G=(V,E)，两个顶点之间的概率表示为w(u,v)。

定义： w'(u,v) = -log(w(u,v))

从某个节点 s 到某个节点 t 的最短路径是使用 w' 作为权重函数时图中的最短路径。您可以使用 Dijkstra's algorithm or Bellman-Ford algorithm

找到最短路径

证明：

对于路径v1->v2->...->vn，它的概率是w(v1,v2) * w(v2,v3) * ... * w(vn-1,vn)。

当使用w'作为权重时，这条路径在使用任何最短路径算法时的代价是：

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))

这显然也适用于从 s 到 t 找到的最小路径。
这意味着此路径的最小值为：

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

而且log是单调函数，所以也是-1 * w(s,v2) * w(v2,v3) * ... * w(vn-1,t)的最小值，是w(s,v2) * w(v2,v3) * ... * w(vn-1,t)的最大值，也就是概率

如何在有向图中找到路径的概率？

How to find probability of path in a directed graph?

algorithm

graph

graph-theory

weighted