1514. Path with Maximum Probability

题目信息

题号:

1514

难度:

Medium

主题:

图、最短路变体、优先队列、概率乘积

原题:

LeetCode 1514

重点:

无向边的成功概率沿路径相乘;寻找从起点到终点乘积最大的路径,不可达时返回 0

题目重述

给定含 n 个节点的无向图,节点编号为 0 到 n-1。edges[i] 的两个端点之间存在一条边,沿该边成功通过的概率为 succProb[i]。

一条路径的成功概率等于路径上所有边概率的乘积。请返回从 start_node 到 end_node 的最大成功概率;若终点不可达,返回 0。

2 <= n <= 10^4,边数不超过 2 * 10^4,每个概率位于 [0,1]。

自建示例

更多边的路径可能拥有更高乘积:

输入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start_node = 0, end_node = 2
输出:0.25
解释:路径 0 -> 1 -> 2 的概率为 0.5 * 0.5 = 0.25,高于直接边的 0.2。

终点不连通时概率为零:

输入:n = 3, edges = [[0,1]], succProb = [0.9], start_node = 0, end_node = 2
输出:0.0
解释:不存在从节点 0 到节点 2 的路径。