概率最大的路径Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个由 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 之间不存在路径

提示：

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

# 思路

链式前向星+dijkstra+堆优化

# 解法

class Solution {
    int[] he, e, ne;
    double[] w;
    int n, cnt, m;

    void add(int a, int b, double c) {
        ne[cnt] = he[a];
        e[cnt] = b;
        w[cnt] = c;
        he[a] = cnt++;
    }

    public double maxProbability(int _n, int[][] edges, double[] prob, int start_node, int end_node) {
        n = _n;
        m = edges.length * 2 + 10;
        he = new int[n];
        e = new int[m];
        w = new double[m];
        ne = new int[m];
        Arrays.fill(he, -1);
        for (int i = 0; i < edges.length; ++i) {
            add(edges[i][0], edges[i][1], prob[i]);
            add(edges[i][1], edges[i][0], prob[i]);
        }
        return dijkstra(start_node, end_node);
    }

    double dijkstra(int start, int end) {
        double[] dist = new double[n];
        dist[start] = 1.0;
        boolean[] visited = new boolean[n];
        PriorityQueue<Pair<Integer, Double>> heap = new PriorityQueue<>((a, b) -> Double.compare(b.getValue(), a.getValue()));
        heap.offer(new Pair<>(start, 1.0));
        while (!heap.isEmpty()) {
            Pair<Integer, Double> poll = heap.poll();
            int u = poll.getKey();
            if (u == end) return dist[u];
            if (visited[u]) continue;
            visited[u] = true;
            for (int i = he[u]; i != -1; i = ne[i]) {
                int to = e[i];
                if (dist[to] < dist[u] * w[i]) {
                    dist[to] = dist[u] * w[i];
                    heap.offer(new Pair<>(to,dist[to]));
                }
            }
        }
        return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 总结

分析出几种情况，然后分别对各个情况实现

#Java