重み付けされた確率グラフにパスが存在する確率

Question

したがって、エッジが存在するかどうかを示すグラフがありますが、各エッジが存在するかどうかのすべての確率があります。私は、2つの特定の頂点[A→B]の間のパスが存在する確率を計算する必要があります。つまり、直接エッジ[AB]または複数のエッジ[AC、CB]から構成される間接的なものです。頂点の数は有限であり、既知である。

Answer 1

私のアプローチ：

1. 実行BFS重量は確率

2. ことで隣接リストを構築するためには、今すぐ修正された「最短経路」アルゴリズムを実行します。私は最短経路アルゴリズムを実行するので、 "最短経路"を引用符で囲みます。
   2.1エンドポイントから始めて、例えばB
   2.2これで1つ前のステップに戻ります。これは要素のリストになります。言って、B '
   2.3は、B内のすべての要素まで最も高い確率の計算' と

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

文献Bに行くための最大を得る：http://homepage.cs.uiowa.edu/~hzhang/c31/notes/ch06WGraph.pdf