本题次要和图的遍历求解最短门路相干，能够用 Dijkstra 或者 Bellman-Ford 算法进行解决。
<!-- more -->

原题

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

解题

首次尝试

本来，我想利用树的深度优先搜寻遍历，加上肯定水平的剪枝（就是排除曾经遍历过的节点），实现这道题目，代码如下：

class Solution {    /**     * key为起始点，value为所有相连的点     */    Map<Integer, Set<Integer>> map;    /**     * key为"点A_点B"(A < B)，value为对应的概率     */    Map<String, Double> probMap;    double maxProb = -1;    int end;    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {        map = new HashMap<>(n * 4 / 3 + 1);        probMap = new HashMap<>(succProb.length * 4 / 3 + 1);        this.end = end;        // 结构每个点的相连关系        for (int i = 0; i < edges.length; i++) {            int[] edge = edges[i];            Set<Integer> set = map.computeIfAbsent(edge[0], k -> new HashSet<>());            set.add(edge[1]);            set = map.computeIfAbsent(edge[1], k -> new HashSet<>());            set.add(edge[0]);            String key = edge[0] < edge[1] ? (edge[0] + "_" + edge[1]) : (edge[1] + "_" + edge[0]);            probMap.put(key, succProb[i]);        }        boolean[] visited = new boolean[n];        dp(start, 1, visited);        return maxProb == -1 ? 0 : maxProb;    }    public void dp(int index, double prob, boolean[] visited) {        // 已到起点        if (index == end) {            maxProb = prob > maxProb ? prob : maxProb;            return;        }        // 获取以后点能够达到的所有点        Set<Integer> set = map.get(index);        // 如果以后点达到不了其余点        if (set == null) {            return;        }        // 标记以后点已拜访        visited[index] = true;        // 遍历相邻的点        for (int next : set) {            if (visited[next]) {                continue;            }            String key = index < next ? (index + "_" + next) : (next + "_" + index);                        // 拜访下一个点            dp(next, prob * probMap.get(key), visited);        }        // 退出，将该点标记为未拜访        visited[index] = false;    }}

但很惋惜，超时了。我想了一下，应该是因为没有借用之前曾经计算出来的后果，因而比拟浪费时间。

其工夫复杂度取决于边的数量，假如边的数量是 m ，则工夫复杂度为O(m^2)。

而边 m 与点 n 的关系，m 最小是 0（也就是点之间没有线），最大是 (n - 1) * n / 2，每个点之间都有连线。

因而能够预感，这样的算法效率的确很差。

Dijkstra 算法

定义概览

Dijkstra (迪杰斯特拉)算法是典型的单源最短门路算法，用于计算一个节点到其余所有节点的最短门路。次要特点是以起始点为核心向外层层扩大，直到扩大到起点为止。

留神该算法要求图中不存在负权边。

算法思维

设 G=(V,E) 是一个带权有向图，把图中顶点汇合 V 分成两组：

第一组为已求出最短门路的顶点汇合（用 S 示意，初始时 S 中只有一个源点，当前每求得一条最短门路 , 就将退出到汇合 S 中，直到全副顶点都退出到 S 中，算法就完结了）。

第二组为其余未确定最短门路的顶点汇合（用 U 示意），按最短门路长度的递增秩序顺次把第二组的顶点退出 S 中。

在退出的过程中，总放弃从源点 v 到 S 中各顶点的最短门路长度不大于从源点 v 到 U 中任何顶点的最短门路长度。

此外，每个顶点对应一个间隔，S 中的顶点的间隔就是从 v 到此顶点的最短门路长度。U 中的顶点的间隔，是从 v 到此顶点只包含 S 中的顶点为两头顶点的以后最短门路长度。

算法步骤

  1. 初始时，S 只蕴含源点，即 S ＝{v}，v 的间隔为0。U 蕴含除 v 外的其余顶点，即: U ={其余顶点}，若 v 与 U 中顶点 u 有边，则<u,v>失常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
  2. 从U中选取一个间隔v最小的顶点k，把k，退出S中（该选定的间隔就是v到k的最短门路长度）。
  3. 以k为新思考的两头点，批改U中各顶点的间隔；若从源点v到顶点u的间隔（通过顶点k）比原来间隔（不通过顶点k）短，则批改顶点u的间隔值，批改后的间隔值的顶点k的间隔加上边上的权。
  4. 反复步骤b和c直到所有顶点都蕴含在S中。

执行动画过程如下图

本题解法

class Solution {    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {        // records[i]代表点i相邻的所有点，以及其概率        List<List<Record>> allRecords = new ArrayList<>(n + 1);        for (int i = 0; i < n + 1; i++) {            allRecords.add(new LinkedList<>());        }        // 结构每个点的相连关系        for (int i = 0; i < edges.length; i++) {            int[] edge = edges[i];            List<Record> records = allRecords.get(edge[0]);            records.add(new Record(edge[1], succProb[i]));                        records = allRecords.get(edge[1]);            records.add(new Record(edge[0], succProb[i]));        }        // 利用广度优先搜寻，进行遍历        // 借用优先队列，保障优先遍历以后概率高的        PriorityQueue<Record> queue = new PriorityQueue<>();        // 记录从start到每一个点的概率        double[] result = new double[n];        // 从start开始遍历        queue.offer(new Record(start, 1));        result[start] = 1;        // 开始        while (!queue.isEmpty()) {            // 以后节点            Record record = queue.poll();            int node = record.node;            double prob = record.prob;            // 获取以后点所能达到的其余节点            List<Record> otherNodes = allRecords.get(node);            // 遍历其余节点            for (Record next : otherNodes) {                int nextNode = next.node;                double nextProb = prob * next.prob;                // 如果以后计算出的概率，小于等于之前计算的概率                if (nextProb <= result[nextNode]) {                    // 那么就没有必要持续算了，间接用之前的即可                    continue;                }                                // 更新概率                result[nextNode] = nextProb;                // 如果已到结尾或者以后的概率曾经比到end的小                if (nextNode == end || nextProb < result[end]) {                    // 那么也没有必要持续了                    continue;                }                // 增加节点                queue.offer(new Record(nextNode, nextProb));            }        }        return result[end];    }    class Record implements Comparable<Record> {        int node;        double prob;        public Record(int node, double prob) {            this.node = node;            this.prob = prob;        }        @Override        public int compareTo(Record other) {            if (other == null) {                return -1;            }            if (this.prob == other.prob) {                return this.node - other.node;            }            return this.prob - other.prob > 0 ? -1 : 1;        }    }}

提交OK，执行用时超过了69%的 java 提交记录，看来还有值得优化的中央。

假如边的数量为 m ，点的数量为 n ，则工夫复杂度为O(n + m + nlogn)。

Bellman-Ford 算法

之前有说到 Dijkstra 算法要求不能有负权边，而这个 Bellman-Ford 算法是反对的。

算法步骤

  1. 创立源顶点 v 到图中所有顶点的间隔的汇合 distSet，为图中的所有顶点指定一个间隔值，初始均为 Infinite，源顶点间隔为 0；
  2. 计算最短门路，执行 V - 1 次遍历；对于图中的每条边：如果终点 u 的间隔 d 加上边的权值 w 小于起点 v 的间隔 d，则更新起点 v 的间隔值 d；
  3. 检测图中是否有负权边造成了环，遍历图中的所有边，计算 u 至 v 的间隔，如果对于 v 存在更小的间隔，则阐明存在环；

例如，上面的有向图 G 中蕴含 5 个顶点和 8 条边。假如源点 为 A。初始化 distSet 所有间隔为 INFI，源点 A 为 0。

因为图中有 5 个顶点，依照步骤 1 须要遍历 4 次，第一次遍历的后果如下。

第二次遍历的后果如下。

以此类推能够得出齐全遍历的后果。

本题解法

class Solution {  public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {    // 记录后果    double[] result = new double[n];    // 终点    result[start] = 1;    // 从start点登程，先更新间接与start点相连的点的概率，而后逐渐更新，直到不须要更新为止    while (true) {      // 是否有过变动      boolean changed = false;      // 遍历所有边      for (int j = 0; j < edges.length; j++) {        int[] edge = edges[j];        // 如果从以后点edge[0]登程，到edge[1]的概率，大于之前记录的后果        if (result[edge[0]] * succProb[j] > result[edge[1]]) {          // 则更新          result[edge[1]] = result[edges[j][0]] * succProb[j];          changed = true;        }        // 因为是无向图,所以再反向遍历        if (result[edge[1]] * succProb[j] > result[edge[0]]) {          result[edge[0]] = result[edge[1]] * succProb[j];          changed = true;        }      }      // 一遍未修改则示意图已遍历实现      if (!changed) {        break;      }    }    return result[end];  }}

提交OK，执行用时超过了95%的 java 提交记录。

其工夫假如边的数量为 m ，点的数量为 n ，则工夫复杂度为O(mn)。

总结

以上就是这道题目我的解答过程了，不晓得大家是否了解了。本题次要和图的遍历求解最短门路相干，能够用 Dijkstra 或者 Bellman-Ford 算法进行解决。

有趣味的话能够拜访我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道