题目

标题和出处

标题：概率最大的路径

出处：1514. 概率最大的路径

难度

7 级

题目描述

要求

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

指定两个结点start \texttt{start}start和end \texttt{end}end，找出从start \texttt{start}start到end \texttt{end}end成功概率最大的路径，并返回其成功概率。

如果不存在从start \texttt{start}start到end \texttt{end}end的路径，返回0 \texttt{0}0。与标准答案的误差不超过10 -5 \texttt{10}^\texttt{-5}10-5的答案视为正确答案。

示例

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 \texttt{n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2}n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000 \texttt{0.25000}0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为0.2 \texttt{0.2}0.2，而另一条为0.5 × 0.5 = 0.25 \texttt{0.5} \times \texttt{0.5} = \texttt{0.25}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 \texttt{n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2}n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000 \texttt{0.30000}0.30000

示例 3：

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

数据范围

• 2 ≤ n ≤ 10 4 \texttt{2} \le \texttt{n} \le \texttt{10}^\texttt{4}2≤n≤104
• 0 ≤ start, end < n \texttt{0} \le \texttt{start, end} < \texttt{n}0≤start, end<n
• start ≠ end \texttt{start} \ne \texttt{end}start=end
• 0 ≤ a, b < n \texttt{0} \le \texttt{a, b} < \texttt{n}0≤a, b<n
• a ≠ b \texttt{a} \ne \texttt{b}a=b
• 0 ≤ succProb.length = edges.length ≤ 2 × 10 4 \texttt{0} \le \texttt{succProb.length} = \texttt{edges.length} \le \texttt{2} \times \texttt{10}^\texttt{4}0≤succProb.length=edges.length≤2×104
• 0 ≤ succProb[i] ≤ 1 \texttt{0} \le \texttt{succProb[i]} \le \texttt{1}0≤succProb[i]≤1
• 每两个结点之间最多有一条边

解法

思路和算法

如果存在一条路径经过k kk条边，其中第i ii条边的成功概率是p i p_ipi​，则该路径的成功概率是p = ∏ i = 1 k p i p = \prod_{i = 1}^{k} p_ip=∏i=1k​pi​，其中0 ≤ p i ≤ 1 0 \le p_i \le 10≤pi​≤1，0 ≤ p ≤ 1 0 \le p \le 10≤p≤1。

定义函数f ( p ) = − log ⁡ p f(p) = -\log pf(p)=−logp，即f ( p ) f(p)f(p)为p pp的对数值的相反数。由于log ⁡ p \log plogp关于p pp单调递增，因此当p pp最大时，f ( p ) f(p)f(p)最小。

将p = ∏ i = 1 k p i p = \prod_{i = 1}^{k} p_ip=∏i=1k​pi​代入f ( p ) f(p)f(p)的表达式，可得f ( p ) = − log ⁡ ∏ i = 1 k p i = ∑ i = 1 k ( − log ⁡ p i ) f(p) = -\log \prod_{i = 1}^{k} p_i = \sum_{i = 1}^{k} (-\log p_i)f(p)=−log∏i=1k​pi​=∑i=1k​(−logpi​)。

当f ( p ) f(p)f(p)最小时，∑ i = 1 k ( − log ⁡ p i ) \sum_{i = 1}^{k} (-\log p_i)∑i=1k​(−logpi​)最小，因此原始问题可以转化成计算最短路径，每条路径的权重是− log ⁡ p i -\log p_i−logpi​。由于0 ≤ p i ≤ 1 0 \le p_i \le 10≤pi​≤1，因此log ⁡ p i ≤ 0 \log p_i \le 0logpi​≤0，− log ⁡ p i ≥ 0 -\log p_i \ge 0−logpi​≥0（这里规定log ⁡ 0 = − ∞ \log 0 = -\inftylog0=−∞），即每条路径的权重都非负，可以使用 Dijkstra 算法计算最短路径。

转化后的问题中的最短路径等价于原始问题中的最大成功概率路径，可以使用 Dijkstra 算法的思想计算从start \textit{start}start到end \textit{end}end的最大成功概率。

为了方便处理，需要首先将边数组转换成邻接列表的形式，转换后可以在O ( 1 ) O(1)O(1)时间获得一个结点的全部相邻结点。

创建长度为n nn的数组probabilities \textit{probabilities}probabilities记录从结点start \textit{start}start到每个结点的最大成功概率，初始时probabilities [ start ] = 1 \textit{probabilities}[\textit{start}] = 1probabilities[start]=1，probabilities \textit{probabilities}probabilities中的其余元素都是0 00。

为了降低时间复杂度，使用 Dijkstra 算法的过程中维护大根堆，初始时大根堆中只有结点start \textit{start}start。每次从大根堆中取出成功概率最大的结点node \textit{node}node，记该结点的概率是probability \textit{probability}probability，对于该结点的每个相邻结点nextNode \textit{nextNode}nextNode，记node \textit{node}node到nextNode \textit{nextNode}nextNode的边的成功概率是nextProbability \textit{nextProbability}nextProbability，执行如下操作。

1. 计算totalProbability = probability × nextProbability \textit{totalProbability} = \textit{probability} \times \textit{nextProbability}totalProbability=probability×nextProbability，则从start \textit{start}start到nextNode \textit{nextNode}nextNode的当前路径的成功概率是totalProbability \textit{totalProbability}totalProbability。

2. 如果probabilities [ nextNode ] < totalProbability \textit{probabilities}[\textit{nextNode}] < \textit{totalProbability}probabilities[nextNode]<totalProbability，则将probabilities [ nextNode ] \textit{probabilities}[\textit{nextNode}]probabilities[nextNode]的值更新为totalProbability \textit{totalProbability}totalProbability，将结点nextNode \textit{nextNode}nextNode加入大根堆。

遍历结束时，probabilities [ end ] \textit{probabilities}[\textit{end}]probabilities[end]即为从start \textit{start}start到end \textit{end}end的最大成功概率。

代码

classSolution{classPair{privateintnode;privatedoubleprobability;publicPair(intnode,doubleprobability){this.node=node;this.probability=probability;}publicintgetNode(){returnnode;}publicdoublegetProbability(){returnprobability;}}publicdoublemaxProbability(intn,int[][]edges,double[]succProb,intstart,intend){List<Pair>[]adjacentArr=newList[n+1];for(inti=0;i<=n;i++){adjacentArr[i]=newArrayList<Pair>();}intm=edges.length;for(inti=0;i<m;i++){int[]edge=edges[i];intnode0=edge[0],node1=edge[1];doubleprobability=succProb[i];adjacentArr[node0].add(newPair(node1,probability));adjacentArr[node1].add(newPair(node0,probability));}double[]probabilities=newdouble[n];probabilities[start]=1;PriorityQueue<Pair>pq=newPriorityQueue<Pair>((a,b)->{if(a.getProbability()==b.getProbability()){return0;}returna.getProbability()<b.getProbability()?1:-1;});pq.offer(newPair(start,1));while(!pq.isEmpty()){Pairpair=pq.poll();intnode=pair.getNode();doubleprobability=pair.getProbability();if(probabilities[node]>probability){continue;}List<Pair>adjacent=adjacentArr[node];for(Pairnext:adjacent){intnextNode=next.getNode();doublenextProbability=next.getProbability();doubletotalProbability=probability*nextProbability;if(probabilities[nextNode]<totalProbability){probabilities[nextNode]=totalProbability;pq.offer(newPair(nextNode,totalProbability));}}}returnprobabilities[end];}}

复杂度分析

• 时间复杂度：O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)，其中n nn是图中的结点数，m mm是图中的边数。将边数组转换成邻接结点列表需要O ( n + m ) O(n + m)O(n+m)的时间，基于大根堆实现的 Dijkstra 算法时间复杂度是O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)，因此时间复杂度是O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)。

• 空间复杂度：O ( n + m ) O(n + m)O(n+m)，其中n nn是图中的结点数，m mm是图中的边数。邻接结点列表需要O ( n + m ) O(n + m)O(n+m)的空间，记录从结点start \textit{start}start到每个结点的最短路径需要O ( n ) O(n)O(n)的空间，优先队列需要O ( n ) O(n)O(n)的空间，因此空间复杂度是O ( n + m ) O(n + m)O(n+m)。