Итак, у меня есть граф, в котором ребра либо существуют, либо нет, и у меня есть все вероятности существования каждого ребра. Мне нужно рассчитать вероятность того, существует ли какой-либо путь между двумя конкретными вершинами [A-> B], что означает прямой край [AB] или косвенный, состоящий из более чем одного края [AC, CB]. Число вершин конечно и известно.Вероятность существования пути в графе взвешенной вероятности
Мой подход:
Теперь запустите модифицированный алгоритм "кратчайшего пути". Я поставил «самый короткий путь» в кавычках, поскольку мы будем запускать алгоритм самого длинного пути.
2.1 Начните с конечной точки, скажем B
2.2 Теперь вернитесь на один шаг, это будет список элементов. Скажем, B '
2,3 Вычислить наибольшую вероятность до всех элементов B' и получить максимум для перехода к B
D[i,j] = 0 if i = j and INF otherwise 
Ref: http://homepage.cs.uiowa.edu/~hzhang/c31/notes/ch06WGraph.pdf
Сколько вершин может быть ? – kraskevich
Существование края обусловлено существованием предыдущего ребра. Узнайте о «условной вероятности» – Ripi2