有向循环概率图 - 所有可能路径的概率

解决有向循环概率图中所有可能路径的概率的问题，可以使用深度优先搜索（DFS）算法来实现。下面是一个示例代码，用于解决这个问题：

from collections import defaultdict

def dfs(graph, start, end, visited, path, probability):
    visited[start] = True
    path.append(start)

    # 如果已经到达目标节点，计算路径的概率并打印
    if start == end:
        print("路径:", path)
        print("概率:", probability)
    
    # 对于每个邻居节点，如果未访问过，则进行DFS
    for neighbor, weight in graph[start]:
        if not visited[neighbor]:
            dfs(graph, neighbor, end, visited, path, probability * weight)
    
    # 恢复状态，以便在其他路径中继续使用节点
    visited[start] = False
    path.pop()

def calculate_path_probability(graph, start, end):
    visited = defaultdict(bool)
    path = []
    probability = 1.0
    
    dfs(graph, start, end, visited, path, probability)

# 示例使用
graph = {
    1: [(2, 0.5), (3, 0.5)],
    2: [(3, 0.25), (4, 0.75)],
    3: [(2, 0.4), (4, 0.6)],
    4: [(1, 0.2), (3, 0.8)]
}

start = 1
end = 4

calculate_path_probability(graph, start, end)

上述代码中，我们使用了一个字典来表示有向循环概率图，其中键表示节点，值表示该节点的邻居节点及其边的权重。我们使用DFS算法来遍历所有可能的路径。在DFS的过程中，我们使用一个布尔型的visited字典来跟踪访问过的节点，使用一个列表path来存储当前路径，使用一个浮点数probability来表示路径的概率。

在DFS的递归函数中，我们首先将当前节点标记为已访问，并将其添加到路径中。然后，我们检查是否到达了目标节点。如果是，则打印路径和概率。否则，我们遍历当前节点的邻居节点，如果邻居节点未访问过，则进行DFS。在递归调用DFS时，我们将概率乘以当前边的权重，以计算路径的概率。

在DFS完成后，我们恢复状态，以便在其他路径中继续使用节点。

最后，我们使用示例图和起始节点、目标节点调用calculate_path_probability函数来计算所有可能路径的概率。