概率最大的路径

难度: Medium

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25

示例 2：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000

示例 3：

输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径

提示：

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每两个节点之间最多有一条边

Submission

运行时间: 121 ms

内存: 26.2 MB

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        g =[[] for i in range(n)]
        for i,(x,y) in enumerate(edges):
            g[x].append((succProb[i],y))
            g[y].append((succProb[i],x))
        # d = [[inf]*n for i in range(n)]
        q = [(-1,start_node)]
        vis = [0]*n
        while q:
            x,y = heapq.heappop(q)
            if y==end_node:
                return -x
            if not vis[y]:
                vis[y]=1
                for xx,yy in g[y]:
                    if not vis[yy]:
                        heapq.heappush(q,(x*xx,yy))
        return 0

Explain

这道题使用了图的最短路径算法的变种来寻找最大成功概率的路径。它使用了优先队列（堆）来实现一个类似于Dijkstra算法的过程，但是由于我们寻找的是最大概率而不是最短距离，我们在堆中存储的是概率的负值，以便最大概率的路径可以优先被处理。算法首先建立了一个图的邻接表表示，然后使用优先队列迭代地选择当前最大概率路径直到到达终点或队列为空，最后如果到达终点则返回当前的概率，否则返回0。

时间复杂度: O(E log E)

空间复杂度: O(N + E)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        g =[[] for i in range(n)] # 创建图的邻接表
        for i,(x,y) in enumerate(edges):
            g[x].append((succProb[i],y)) # 添加节点x到y的边和对应概率
            g[y].append((succProb[i],x)) # 无向图，同样添加节点y到x的边和对应概率
        q = [(-1,start_node)] # 优先队列，存储(-概率, 节点)以获取最大概率
        vis = [0]*n # 访问数组，避免重复处理节点
        while q:
            x,y = heapq.heappop(q) # 弹出当前概率最大的节点
            if y==end_node:
                return -x # 如果到达终点，返回当前概率（负号转正）
            if not vis[y]:
                vis[y]=1 # 标记节点已访问
                for xx,yy in g[y]:
                    if not vis[yy]:
                        heapq.heappush(q,(x*xx,yy)) # 将当前节点的相邻节点和路径概率压入堆中
        return 0 # 无法到达终点时返回0

Explore

在求解最大概率路径的问题中，使用优先队列（堆）而不是队列或栈的主要原因是优先队列能够保证每次从队列中取出的是当前未处理节点中概率最大的节点。这是类似于Dijkstra算法的工作原理，它适用于处理带权重的图的最短路径问题，在这种场景下，权重是节点间的概率。优先队列的这种属性使得算法能够更加高效地向目标节点逼近，而不必遍历所有可能的路径。使用普通队列的广度优先搜索（BFS）或使用栈的深度优先搜索（DFS）虽然也能够遍历图，但在找到最大概率路径方面效率较低，因为它们无法保证每次处理的都是最有希望的节点。

在优先队列中使用概率的负值的主要考虑是Python中的优先队列（使用heapq实现）默认是最小堆，这意味着它总是先出队列中最小的元素。为了使算法能够优先处理最大概率的路径，我们通过存储概率的负值来逆转这一默认行为，使得数值上最小的（即最大的负数）对应于原始概率中数值上最大的。这种表示方式的优势在于，我们可以利用现有的最小堆数据结构来模拟最大堆的行为，从而简化代码实现并提高算法的效率。

题解中的算法似乎没有明确处理图中存在多条边连接同一对节点的情况，即可能未直接合并或选择概率。在这种情况下，邻接表可能会包含多个条目来表示同一对节点之间的不同概率的边。算法在处理时会考虑这些边作为独立的路径来处理。在实际应用中，如果需要优化，可以在构建图的邻接表时合并或选择最大的概率，只保留每对节点之间概率最大的边，这样可以简化图的结构并可能提高算法的效率。