1514. 最大成功概率路径
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个无向加权图，任务是找到从起点到终点的最大成功概率路径。如果没有路径，返回0。可以使用修改后的Dijkstra算法，通过优先队列探索概率最高的路径。
🔎
延伸解读
概率相乘与精度处理
在计算路径成功概率时，需要将各边概率相乘。但浮点数连续相乘可能引入精度误差，影响结果。文章提示可将概率取对数，将乘法转换为加法，再使用Dijkstra算法求最短路径（取负后）。这样能有效减少误差，尤其当路径较长时。
最大概率路径的算法选择
该问题可视为最短路径的变体，但目标是最大化概率而非最小化距离。使用修改的Dijkstra算法，通过最大堆优先探索概率最高的路径，能高效找到最优解。由于概率值在0到1之间，乘法会使数值递减，因此优先队列需按概率从大到小排序。
边界情况与返回值
当起点和终点之间不存在路径时，函数应返回0。此外，起点到自身的概率初始化为1，但题目保证start != end。算法需处理节点数最多10^4、边数最多2*10^4的规模，使用邻接表和优先队列可满足性能要求。
❓
Q&A
如何在无向加权图中找到最大成功概率路径？
可以使用修改后的Dijkstra算法，通过优先队列探索概率最高的路径。
如果起点和终点之间没有路径，应该返回什么？
如果没有路径，返回0。
图的表示方式是什么？
图的表示为邻接表，每个节点指向其邻居及连接它们的边的成功概率。
如何处理概率计算中的精度问题？
可以通过取对数概率来避免乘法带来的精度错误。
在算法中如何初始化起点的概率？
初始化起点的概率为1，表示停留在起点的概率为1。
使用最大堆的目的是什么？
使用最大堆（优先队列）优先探索概率最高的路径，以确保找到最大概率的路径。
🏷️
