1514。具有最大概率的路径
难度:中等
主题:数组、图、堆(优先级队列)、最短路径
给你一个由 n 个节点(0 索引)组成的无向加权图,由边列表表示,其中edges[i] = [a, b] 是连接节点 a 和 b 的无向边,有成功的概率遍历该边 succProb[i].
给定两个节点的起点和终点,找到从起点到终点成功概率最大的路径,并返回其成功概率。
如果没有从起点到终点的路径,返回0。如果您的答案与正确答案相差最多 1e-5.
,我们将接受您的答案。示例1:
示例2:
示例 3:
约束:
提示:
解决方案:
我们可以使用 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)用于首先探索概率最高的路径。这对于确保当我们到达目标节点时,找到概率最大的路径至关重要。
算法:
对于提供的示例:
$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 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
以上是具有最大概率的路径的详细内容。更多信息请关注PHP中文网其他相关文章!