具有最大概率的路径

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！=b
• 0
• 0
• 每两个节点之间最多有一条边

提示：

1. 乘以概率会导致精度误差。
2. 采用对数概率对数字进行求和而不是相乘。
3. 使用 Dijkstra 算法求否定所有成本后两个节点之间的最小路径。

解决方案：

我们可以使用 Dijkstra 算法的修改版本。您将最大化成功的可能性，而不是寻找最短路径。

让我们用 PHP 实现这个解决方案：1514。具有最大概率的路径

雷雷

解释：

1. 图表示：图表示为邻接列表，其中每个节点都指向其邻居以及连接它们的边的成功概率。

2. 最大概率数组：数组maxProb用于存储从起始节点到达每个节点的最大概率。

3. 优先队列：最大堆（SplPriorityQueue）用于首先探索概率最高的路径。这对于确保当我们到达目标节点时，找到概率最大的路径至关重要。

4. 算法:

   • 将起始节点的概率初始化为1（因为停留在起始点的概率为1）。
   • 使用优先级队列来探索节点，更新到达每个邻居的最大概率。
   • 如果到达目的节点，则返回概率。
   • 如果不存在路径，则返回0.

输出：

对于提供的示例：

雷雷

输出将为 0.25.

这种方法确保了使用 Dijkstra 算法的有效解决方案，同时处理概率计算的细节。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给存储库一颗星，或者在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是具有最大概率的路径的详细内容。更多信息请关注PHP中文网其他相关文章！