文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题概率最大的路径出处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.50.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≤1040 ≤ start, end n \texttt{0} \le \texttt{start, end} \texttt{n}0≤start, endnstart ≠ end \texttt{start} \ne \texttt{end}startend0 ≤ a, b n \texttt{0} \le \texttt{a, b} \texttt{n}0≤a, bna ≠ b \texttt{a} \ne \texttt{b}ab0 ≤ 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.lengthedges.length≤2×1040 ≤ 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∏i1k​pi​其中0 ≤ p i ≤ 1 0 \le p_i \le 10≤pi​≤10 ≤ 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∏i1k​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∏i1k​pi​∑i1k​(−logpi​)。当f ( p ) f(p)f(p)最小时∑ i 1 k ( − log ⁡ p i ) \sum_{i 1}^{k} (-\log p_i)∑i1k​(−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]1probabilities \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执行如下操作。计算totalProbability probability × nextProbability \textit{totalProbability} \textit{probability} \times \textit{nextProbability}totalProbabilityprobability×nextProbability则从start \textit{start}start到nextNode \textit{nextNode}nextNode的当前路径的成功概率是totalProbability \textit{totalProbability}totalProbability。如果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.nodenode;this.probabilityprobability;}publicintgetNode(){returnnode;}publicdoublegetProbability(){returnprobability;}}publicdoublemaxProbability(intn,int[][]edges,double[]succProb,intstart,intend){ListPair[]adjacentArrnewList[n1];for(inti0;in;i){adjacentArr[i]newArrayListPair();}intmedges.length;for(inti0;im;i){int[]edgeedges[i];intnode0edge[0],node1edge[1];doubleprobabilitysuccProb[i];adjacentArr[node0].add(newPair(node1,probability));adjacentArr[node1].add(newPair(node0,probability));}double[]probabilitiesnewdouble[n];probabilities[start]1;PriorityQueuePairpqnewPriorityQueuePair((a,b)-{if(a.getProbability()b.getProbability()){return0;}returna.getProbability()b.getProbability()?1:-1;});pq.offer(newPair(start,1));while(!pq.isEmpty()){Pairpairpq.poll();intnodepair.getNode();doubleprobabilitypair.getProbability();if(probabilities[node]probability){continue;}ListPairadjacentadjacentArr[node];for(Pairnext:adjacent){intnextNodenext.getNode();doublenextProbabilitynext.getProbability();doubletotalProbabilityprobability*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((nm)logn)其中n nn是图中的结点数m mm是图中的边数。将边数组转换成邻接结点列表需要O ( n m ) O(n m)O(nm)的时间基于大根堆实现的 Dijkstra 算法时间复杂度是O ( ( n m ) log ⁡ n ) O((n m) \log n)O((nm)logn)因此时间复杂度是O ( ( n m ) log ⁡ n ) O((n m) \log n)O((nm)logn)。空间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的结点数m mm是图中的边数。邻接结点列表需要O ( n m ) O(n m)O(nm)的空间记录从结点start \textit{start}start到每个结点的最短路径需要O ( n ) O(n)O(n)的空间优先队列需要O ( n ) O(n)O(n)的空间因此空间复杂度是O ( n m ) O(n m)O(nm)。