1514。具有最大概率的路径
难度：中等
主题：数组、图、堆（优先队列）、最短路径
给定一个由 n 个节点（0 索引）组成的无向加权图，由边列表表示，其中edges[i] = [a, b] 是连接节点 a 和 b 的无向边，具有遍历成功的概率该边 succprob[i].
给定两个节点的起点和终点，找到从起点到终点成功概率最大的路径并返回其成功概率.
如果没有从起点到终点的路径，返回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 0 开始！=结束0 a！=b0 0 每两个节点之间最多有一条边
提示：
- 乘以概率会导致精度误差。采用对数概率对数字进行求和而不是相乘。使用 dijkstra 算法求否定所有成本后两个节点之间的最小路径。
解决方案：
我们可以使用 dijkstra 算法的修改版本。您将最大化成功的可能性，而不是寻找最短路径。
让我们用 php 实现这个解决方案：1514。具有最大概率的路径
<?php/** * @param integer $n * @param integer[][] $edges * @param float[] $succprob * @param integer $start_node * @param integer $end_node * @return float */function maxprobability($n, $edges, $succprob, $start_node, $end_node) { … … … /** * go to ./solution.php */}// example usage:$n1 = 3;$edges1 = [[0,1],[1,2],[0,2]];$succprob1 = [0.5,0.5,0.2];$start_node1 = 0;$end_node1 = 2;echo maxprobability($n1, $edges1, $succprob1, $start_node1, $end_node1);//output: 0.25000$n2 = 3;$edges2 = [[0,1],[1,2],[0,2]];$succprob2 = [0.5,0.5,0.3];$start_node2 = 0;$end_node2 = 2;echo maxprobability($n2, $edges2, $succprob2, $start_node2, $end_node2);//output: 0.30000$n3 = 3;$edges3 = [[0,1]];$succprob3 = [0.5;$start_node3 = 0;$end_node3 = 2;echo maxprobability($n3, $edges3, $succprob3, $start_node3, $end_node3); //output: 0.00000?>
解释：
图表示：图表示为邻接列表，其中每个节点都指向其邻居以及连接它们的边的成功概率。
最大概率数组：数组maxprob用于存储从起始节点到达每个节点的最大概率。
优先队列：最大堆（splpriorityqueue）用于首先探索概率最高的路径。这对于确保当我们到达目的地节点时，我们找到概率最大的路径是至关重要的。
算法:
将起始节点的概率初始化为1（因为停留在起始点的概率为1）。使用优先级队列来探索节点，更新到达每个邻居的最大概率。如果到达目的节点，则返回概率。如果不存在路径，则返回0.
输出：
对于提供的示例：
$n = 3;$edges = [[0,1],[1,2],[0,2]];$succProb = [0.5,0.5,0.2];$start_node = 0;$end_node = 2;
输出将为 0.25.
这种方法确保了使用 dijkstra 算法的有效解决方案，同时处理概率计算的细节。
联系链接
如果您发现本系列有帮助，请考虑在 github 上给存储库 一颗星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
领英github
以上就是具有最大概率的路径的详细内容，更多请关注范的资源库其它相关文章！
