1514. Path with Maximum Probability¶
题目信息¶
- 题号:
1514
- 难度:
Medium
- 主题:
图、最短路变体、优先队列、概率乘积
- 原题:
- 重点:
无向边的成功概率沿路径相乘;寻找从起点到终点乘积最大的路径,不可达时返回
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 的路径。