Leetcode 1514，概率最大的路径

Leetcode 1514 问题描述

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 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 之间不存在路径

Dijkstra

Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值（原则上为贪心算法，如果存在负值边，无法保证算法正确性，在《算法导论》24.3中详细证明了该正确性。）
Dijkstra算法在运行过程中维持的关键信息是一组结点集合S。从源结点s到该集合中每个结点之间的最短路径已经被找到。算法能够重复从结点集V-S中选择最短路径估计最小的结点u，将u从V中加入到S，然后对所有从u发出的边进行松弛（在单源最短路径问题上需要松弛技术，对于一个结点v来说，维持一个属性v.d，用来记录源结点s到结点v的最短路径权重的上界，称v.d为s到v的最短路径估计。而对一条边（u，v）的松弛过程为首先测试是否可以对s到v的最短路径进行改善。将从结点s到结点u之间的最短路径距离加上u到v之间的边权重，并与当前s到v的最短路径距离进行比较，如果前者小，则同时更新最短路径v.d和v结点的前驱结点parent）。
Dijkstra算法使用贪心策略，总是选择集合V-S中最近的结点来加入集合S中，并通过松弛操作，不断地更新最短路径和每个结点的前驱结点。

参考资料

https://www.bilibili.com/video/BV1mt411i7DX?from=search&seid=13050856158988471531
通过动画详细地讲述了Dijkstra算法的理念，能够对算法有一定认识，了解怎么得到最短路径的过程。

https://www.bilibili.com/video/BV1ts41157Sy?from=search&seid=7344759299652674015
个人感觉这个收获会更大，更偏重于代码实践一点，对Dijkstra过程的讲解中就介绍了priority queue等思路，整个过程就是写代码时的思路和方法，并且在后半部分有详细的代码，看完那个代码再来做1514就会事半功倍。

代码：

下面展示一下代码：在Dijkstra算法求解问题为最短路径问题，每次对路径执行加法，初始距离置0（start-start的距离），其在priority queue中的优先级可以直接用结点的距离表示，距离越小，则优先级越高，start结点的优先级为0。在1514这个问题，从start到end的概率通过乘法获得，并且求概率的最高值，故对概率值（edge）取反，使start优先级为-1,（即初始概率为-1，乘以任何概率均大于-1，从而实现start优先级最高，概率乘积最高者优先级最高）

class Solution:def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:#通过list构建graphfrom collections import defaultdictst_maps = defaultdict(list)for i, (s, e) in enumerate(edges):st_maps[s].append((e, succProb[i]))st_maps[e].append((s, succProb[i]))pqueue = []#空列表保存所有计算后更新的概率，并一直使最大概率（负值即为最小概率）出栈，当为空栈时遍历graph中所有点。heapq.heappush(pqueue, (-1, start)) #-1乘以概率，保证了start在序列中的优先级最高，且概率越大，优先级越高dist = defaultdict(float)dist[start] = -1  #正常的dijkstra算法为加最小值，此处应为1while pqueue:curdist, cur = heapq.heappop(q)  #出栈当前点以及概率if cur == end:  #如果当前点就是结束点，就可以结束dijkstra算法return -curdistfor node, prob in st_maps[cur]: #对所有与curr节点相连的节点，计算概率，并和当前最大概率比较（因为负值，所以小于）tmp = curdist * probif tmp < dist[node]:  #如果当前概率（负）小于在dist中保存的概率（负），则对dist进行更新，将对应节点和更新的距离入栈。dist[node] = tmpheapq.heappush(q, (tmp, node))return 0