在加權概率圖中存在路徑的概率

Question

所以，我有一個圖，其中邊或者存在或者不存在，並且我具有每個邊是否存在的所有概率。我需要計算兩個特定頂點[A-> B]之間是否存在任何路徑的概率，即直接邊[AB]或由多個邊[AC，CB]組成的間接路徑。頂點的數量是有限的且已知的。

Answer 1

我的方法：

1. 運行BFS建立與權重爲概率

2. 現在運行修改的「最短路徑」算法鄰接表。我將「最短路徑」放在引號中，因爲我們將運行最長的路徑算法。
   2.1從終點開始，說B
   2.2現在回頭一步，這將是一個元素列表。說，B '
   2.3計算最高可能性，直到B中的所有元素'，並獲得最大的換去到B

   D[i,j] = 0 if i = j and INF otherwise

編號：http://homepage.cs.uiowa.edu/~hzhang/c31/notes/ch06WGraph.pdf