Medium

题目描述

给你一个由 n 个节点（节点编号从 0 到 n-1）组成的无向加权图，该图由一个边列表 edges 表示，其中 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 之间不存在路径。

提示：

  • 2 <= n <= 10^4
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10^4
  • 0 <= succProb[i] <= 1
  • 任意两个节点之间最多只有一条边。

解题思路

这是一个在图中寻找最大概率路径的问题，本质上是最短路径问题的变形。

核心思路： 由于路径概率是各边概率的乘积，我们需要找到概率乘积最大的路径。直接处理概率乘积会遇到精度问题，因此可以采用取对数的技巧：

  1. 对数转换：将概率取负对数，这样概率乘积的最大化问题转化为路径权重和的最小化问题
  2. Dijkstra算法：使用优先队列（最大堆）实现Dijkstra算法，寻找最大概率路径

算法步骤：

  1. 构建邻接表表示图结构
  2. 使用Dijkstra算法，维护到每个节点的最大概率
  3. 优先队列存储(概率, 节点)对，每次取出概率最大的节点
  4. 更新相邻节点的最大概率
  5. 返回到终点的最大概率

时间复杂度分析： Dijkstra算法的时间复杂度为O((V+E)logV)，其中V是节点数，E是边数。

空间复杂度分析： 需要存储邻接表和优先队列，空间复杂度为O(V+E)。

代码实现

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        vector<vector<pair<int, double>>> graph(n);
        
        // 构建邻接表
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1];
            double prob = succProb[i];
            graph[u].push_back({v, prob});
            graph[v].push_back({u, prob});
        }
        
        vector<double> maxProb(n, 0.0);
        maxProb[start_node] = 1.0;
        
        priority_queue<pair<double, int>> pq;
        pq.push({1.0, start_node});
        
        while (!pq.empty()) {
            auto [prob, node] = pq.top();
            pq.pop();
            
            if (node == end_node) {
                return prob;
            }
            
            if (prob < maxProb[node]) {
                continue;
            }
            
            for (auto [neighbor, edgeProb] : graph[node]) {
                double newProb = prob * edgeProb;
                if (newProb > maxProb[neighbor]) {
                    maxProb[neighbor] = newProb;
                    pq.push({newProb, neighbor});
                }
            }
        }
        
        return 0.0;
    }
};

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        import heapq
        from collections import defaultdict
        
        graph = defaultdict(list)
        
        # 构建邻接表
        for i in range(len(edges)):
            u, v = edges[i]
            prob = succProb[i]
            graph[u].append((v, prob))
            graph[v].append((u, prob))
        
        max_prob = [0.0] * n
        max_prob[start_node] = 1.0
        
        # 使用负数实现最大堆
        pq = [(-1.0, start_node)]
        
        while pq:
            prob, node = heapq.heappop(pq)
            prob = -prob
            
            if node == end_node:
                return prob
            
            if prob < max_prob[node]:
                continue
            
            for neighbor, edge_prob in graph[node]:
                new_prob = prob * edge_prob
                if new_prob > max_prob[neighbor]:
                    max_prob[neighbor] = new_prob
                    heapq.heappush(pq, (-new_prob, neighbor))
        
        return 0.0

public class Solution {
    public double MaxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        var graph = new List<(int, double)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, double)>();
        }
        
        // 构建邻接表
        for (int i = 0; i < edges.Length; i++) {
            int u = edges[i][0], v = edges[i][1];
            double prob = succProb[i];
            graph[u].Add((v, prob));
            graph[v].Add((u, prob));
        }
        
        double[] maxProb = new double[n];
        maxProb[start_node] = 1.0;
        
        var pq = new PriorityQueue<(double prob, int node), double>(
            Comparer<double>.Create((x, y) => y.CompareTo(x))
        );
        pq.Enqueue((1.0, start_node), 1.0);
        
        while (pq.Count > 0) {
            var (prob, node) = pq.Dequeue();
            
            if (node == end_node) {
                return prob;
            }
            
            if (prob < maxProb[node]) {
                continue;
            }
            
            foreach (var (neighbor, edgeProb) in graph[node]) {
                double newProb = prob * edgeProb;
                if (newProb > maxProb[neighbor]) {
                    maxProb[neighbor] = newProb;
                    pq.Enqueue((newProb, neighbor), newProb);
                }
            }
        }
        
        return 0.0;
    }
}

var maxProbability = function(n, edges, succProb, start_node, end_node) {
    const graph = Array.from({length: n}, () => []);
    
    for (let i = 0; i < edges.length; i++) {
        const [a, b] = edges[i];
        const prob = succProb[i];
        graph[a].push([b, prob]);
        graph[b].push([a, prob]);
    }
    
    const maxProb = new Array(n).fill(0);
    maxProb[start_node] = 1;
    
    const pq = [[1, start_node]];
    
    while (pq.length > 0) {
        pq.sort((a, b) => b[0] - a[0]);
        const [currentProb, node] = pq.shift();
        
        if (node === end_node) {
            return currentProb;
        }
        
        if (currentProb < maxProb[node]) {
            continue;
        }
        
        for (const [neighbor, edgeProb] of graph[node]) {
            const newProb = currentProb * edgeProb;
            if (newProb > maxProb[neighbor]) {
                maxProb[neighbor] = newProb;
                pq.push([newProb, neighbor]);
            }
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O((V+E)logV)，其中 V 是节点数，E 是边数。Dijkstra算法的标准复杂度
空间复杂度O(V+E)，需要存储邻接表和优先队列

相关题目