Bellman-Ford算法

贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种。它的原理是对图进行次松弛操作，得到所有可能的最短路径；因为负权环可以无限制的降低总花费，所以如果发现第 n次操作仍可降低花销，就一定存在负权环。

必要入参：
节点数量：n
节点路径：path[][]
路径值：pv
起点：start
终点：end

一般过程：

1. 创建节点最优解数组dp[n];
2. 初始化最优解数组;如果是求最小值，将dp数组所有值初始化至最大，并有dp[strat]初始化至最小；如果求最大值，将dp数组所有值初始化至最小，将dp[strat]初始化至最大；如计算步长时（加法），最大值为Integer.MAX_VALUE，最小值为0；计算概率时（乘法），最大值为1，最小值为0；
3. 遍历节点列表进行松弛操作；至多循环n-1次，如果超过次数返回失败值（一般是0）；
4. 判断并更新对应dp值；求最大值：dp[u]+w(u,v)>dp[v]则更新，求最小值：dp[u]+w(u,v)<dp[v]则更新；dp[v]=dp[u]+w(u,v)
5. 如果在一次循环中没有进行松弛操作，则完成全部松弛操作，返回dp[end]

例题：
给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。如果不存在从 start 到 end 的路径，请 返回 0 。
来源：力扣（LeetCode）

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //创建并初始化最优解数组
        double dp[] = new double[n];
        //初始化最优解数组
        //由于初始化为0，所以不需要循环赋值
        //for (int i = 0; i < n; i++) {
        //    dp[i] = 0;
        //}
        //初始化起点
        dp[start] = 1;
        //遍历节点列表进行松弛操作
        int count = 1;
        while (count < n) {//至多循环n-1次，如果超过次数返回失败值
            boolean k = false;
            for (int j = 0; j < edges.length; j++) {
                //判断并更新对应dp值，求最大值
                if (dp[edges[j][0]] * succProb[j] > dp[edges[j][1]]) {
                    dp[edges[j][1]] = dp[edges[j][0]] * succProb[j];
                    k = true;
                }
                //因为是无向图,所以再反向遍历
                if (dp[edges[j][1]] * succProb[j] > dp[edges[j][0]]) {
                    dp[edges[j][0]] = dp[edges[j][1]] * succProb[j];
                    k = true;
                }
            }
            if (!k) break;//循环一遍未修改，则表示已完成松弛操作
            count++;
        }
        if (count >= n) {
            //如果循环超过n-1次返回失败值
            return 0;
        } else {
            return dp[end];
        }
    }

2020-07-20