Wahrscheinlichkeit der Existenz eines Pfades in einem gewichteten Wahrscheinlichkeitsdiagramm

Question

So habe ich ein Diagramm, in dem die Kanten entweder existieren oder nicht, und ich habe alle Wahrscheinlichkeiten, ob jede Kante existiert. Ich muss die Wahrscheinlichkeit berechnen, ob irgendein Pfad zwischen zwei bestimmten Knoten [A -> B] existiert, dh eine direkte Kante [AB] oder eine indirekte Kante, die aus mehr als einer Kante besteht [AC, CB]. Die Anzahl der Ecken ist endlich und bekannt.

Answer 1

Mein Ansatz:

1. Run BFS eine Adjazenzliste mit dem Gewicht ist die Wahrscheinlichkeit,

2. Jetzt laufen eine modifizierte "kürzesten Weg" Algorithmus zu bauen. Ich gebe den "kürzesten Pfad" in Anführungszeichen ein, da wir den Algorithmus für den längsten Pfad ausführen.
   2.1 Start vom Endpunkt, sagen B
   2.2 Jetzt gehen Sie einen Schritt zurück, das wird eine Liste von Elementen sein. Sprich, B '
   2.3 Berechnen Sie die höchste Wahrscheinlichkeit, bis alle Elemente in B' und erhalten max für den Gang

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

Ref nach B: http://homepage.cs.uiowa.edu/~hzhang/c31/notes/ch06WGraph.pdf