最近网上有人列出了曾经在阿里巴巴上过班并离职创业成功的十位大佬，不得不说阿里巴巴确实在向社会输入人才。 这里面孙彤宇是阿里巴巴初创团队成员之一，1999 年阿里巴巴刚成立的时候就加入了，2003 年受马云指派创建淘宝网，后任淘宝网总裁、阿里巴巴副总裁等职，2008 年 3 月离职。 而何小鹏在2004 年联合创立 UC 优视，打造用户超 4 亿的 UC 浏览器，后来被阿里巴巴收购，在后来离职创办小鹏汽车，也算是在阿里上过班。 
--------------下面是今天的算法题-------------- 来看下今天的算法题，这题是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]], succProb = [0.5], start = 0, end = 2 输出：0.00000 解释：节点 0 和 节点 2 之间不存在路径
问题分析 这题说的是计算从起始点到终点成功概率的最大路径，并返回其成功的概率。每条边都有一个成功的概率值，如果没有概率值就非常简单了，我们可以使用BFS或者迪杰斯特拉算法。 每条边虽然有概率值，但不影响我们计算，这个概率值就相当于边的权值，但计算的时候不是累加，而是相乘。这里我们可以使用，使用堆优化的方式来解。 刚开始的时候把起始点添加到堆中，然后遍历堆，堆顶元素出堆之后，计算和它相连的顶点，如果相连的顶点没有出堆，就把相连的顶点添加到堆中，继续遍历堆，直到遇到出堆的元素是终点为止，顶点是否出堆可以用visited数组记录。 JAVA： class Pair implements Comparable
{ int v = 0; double p = 0; public Pair(int v, double p) { this.v = v; this.p = p; } @Override public int compareTo(Pair pair) { return Double.compare(pair.p, this.p);// 根据概率从大到小排序。 } } public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) { // 把图转化为邻接表 List [] g = new List[n]; for (int i = 0; i < n; i++) g[i] = new ArrayList<>(); for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; double p = succProb[i]; g[u].add(new Pair(v, p)); g[v].add(new Pair(u, p)); } boolean[] visited = newboolean[n];// 标记顶点是否已经出堆。 PriorityQueue pq = new PriorityQueue<>();// 堆 pq.offer(new Pair(start_node, 1));// 起始点添加到堆中 while (!pq.isEmpty()) { Pair cur = pq.poll(); int v = cur.v; double p = cur.p; if (v == end_node) return p; visited[v] = true;// 标记在堆中，顶点在出堆之前是可以多次入堆的。 for (Pair pair : g[v]) { if (!visited[pair.v]) { pq.offer(new Pair(pair.v, pair.p * p)); } } } return0; }
C++： struct Pair { int v; double p; Pair(int v, double p) : v(v), p(p) {} // 重载比较运算符，根据概率从大到小排序 booloperator<(const Pair &other) const { return p < other.p; } }; public: double maxProbability(int n, vector
> &edges, vector
&succProb, int start_node, int end_node) { // 把图转化为邻接表 vector
g(n); for (int i = 0; i < edges.size(); ++i) { int u = edges[i][0]; int v = edges[i][1]; double p = succProb[i]; g[u].emplace_back(v, p); g[v].emplace_back(u, p); } vector
visited(n, false); // 标记顶点是否已经出堆 priority_queue pq; // 优先队列（堆） pq.emplace(start_node, 1); // 起始点添加到堆中 while (!pq.empty()) { Pair cur = pq.top(); pq.pop(); int v = cur.v; double p = cur.p; if (v == end_node) return p; visited[v] = true; // 标记在堆中，顶点在出堆之前是可以多次入堆的 for (constauto &pair: g[v]) { if (!visited[pair.v]) { pq.emplace(pair.v, pair.p * p); } } } return0; }
笔者简介 博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧 。
| 
