使用Python查找最大概率路径的程序

假设我们有一个无向带权图，有n个节点（节点从0开始编号）。该图使用边列表作为输入，对于每条边e，它有穿过该边的成功概率probability[e]。我们还有起点和终点，我们必须找到从起点到终点具有最大成功概率的路径并返回其成功概率。如果找不到任何路径，则返回0。

因此，如果输入是这样的

使用Python查找最大概率路径的程序

那么输出将是0.24，因为从节点0到2有两条路径，一条路径的概率是0.2，另一条经过节点1的概率是0.4*0.6=0.24，这是最大的。

要解决这个问题，我们可以按照以下步骤进行−

g: =从给定的边列表构建图形，并使用概率值作为权重
q: =队列数据结构
将(start,1)插入q
visited: = map，用于保存已访问的节点
while q不为空，重复执行以下步骤
- (node,prob): = q的第一个项目并将其从q中删除
- 如果visited[node] > prob，则
  - 进行下一次迭代
- 否则，
  - visited[node] : = prob
- 对于g[node]中的每个相邻节点adj和概率nextProb，执行以下操作
  - 如果visited [adj]< prob* nextProb，则
  - 在q的末尾插入(adj，prob* nextProb)
return visited[end]

让我们查看以下实现，以更好的说明−

更多Python相关文章，请阅读：Python 教程

例子

from collections import defaultdict, deque
def solve(edges, probability, start, end):
   g = defaultdict(list)
   for i in range(len(edges)):
      src, dst = edges[i][0], edges[i][1]
      prob = probability[i]
      g[src].append((dst, prob))
      g[dst].append((src, prob))
   q = deque()
   q.append((start, 1))
   visited = defaultdict(int)
   while q:
      node, prob = q.popleft()
      if visited[node] > prob:
         continue
      else:
         visited[node] = prob
      for adj, nextProb in g[node]:
         if visited[adj] < prob* nextProb:
            q.append((adj, prob* nextProb))
   return visited[end]
edges = [[0,1],[1,2],[0,2]]
probability = [0.5,0.5,0.2]
start = 0
end = 2
print(solve(edges, probability, start, end))