一、BellMan-Ford算法简介

  与Dijkstra算法一样，BellMan-Ford算法也是用于求有向图和无向图的单源最短路径的算法。但是，BellMan-Ford算法与Dijkstra算法的不同处，有以下2点：
①、BellMan-Ford算法可以用于边的权值为负数的有向图中，但该图中不能存在负值圈，也就是说，BellMan-Ford算法在计算无向图时，该无向图不能存在负值边（无向图的负值边就会存在负值圈），Dijkstra算法所计算的有向图和无向图中，边的权值都不能为负数；
②、BellMan-Ford算法是通过对边进行|V|-1次松弛操作来实现的，|V|是图中结点的数量，而Dijkstra算法是通过贪心法，选取未处理的结点中权值最小的结点，然后对选取的结点的邻接边进行松弛操作。

1.1、BellMan-Ford算法的松弛函数

  对于边集合E中的任意边，以w(u,v)表示结点u出发到结点v的边（Edge）的权值，以d[v]表示当前从起点s到结点v的路径权值，若存在边w(u,v)，使得：

\[d[v]>d[u]+w(u,v) \]

则更新d[v]的值：

\[d[v]=d[u]+w(u,v) \]

所以松弛函数的作用，就是判断是否经过某个顶点，或者说经过某条边，可以缩短起点到终点的路径权值。

1.2、BellMan-Ford算法中松弛函数的执行次数

  现有所有结点a~d，如下图所示：

  用d[d]表示起点a到结点d的距离，用δ(a,d)表示起点a到结点d的最短路径权值，用p=<a,...,d> 表示结点a到结点d的路径，初始情况d[a]=0，d[v]=∞，v∈V-{a}。以对边集合 E 中每条边执行一次松弛函数作为一次迭代。那么，最好情况和最坏情况的分析，分别如下：
①、最好情况下，如果遍历松弛边的顺序为：w(a,b)，w(b,c)，w(c,d)，其他两条边w(a,c)，w(a,d)顺序无影响；

• 第一次迭代

对边w(a,b)执行松弛函数，则d[b] = d[a]+w(a,b) = 1；
对边w(b,c)执行松弛函数，则d[c] = d[b]+w(b,c) = 3；
对边w(c,d)执行松弛函数，则d[d] = d[c]+w(c,d) = 8；

因为图结构比较简单，所以可以直接由观察得知，经过第一次迭代，即可得出从起点a到所有结点b、c、d的最短路径权值。
②、最坏情况下，如果遍历松弛边的顺序为：w(c,d)，w(b,c)或w(b,c)，w(c,d)，其他三条边w(a,b)，w(a,c)，w(a,d)顺序无影响；

• 第一次迭代

对边w(c,d)执行松弛函数，则d[d] = ∞；
对边w(b,c)执行松弛函数，则d[c] = ∞；
对边w(a,b)执行松弛函数，则d[b] = d[a] + w(a,b) = 1；
对边w(a,c)执行松弛函数，则d[c] = d[a] + w(a,c) = 6；
对边w(a,d)执行松弛函数，则d[d] = d[a] + w(a,d) = 10； 

第一次迭代，有三条边起到了松弛的效果，直观的可以看出 d[b] = δ(a,b)，第一次迭代可以获得起点a到结点b的最短路径，路径为 P=<a,b>；

• 第二次迭代

对边w(c,d)执行松弛函数，则d[d] = 10；
对边w(b,c)执行松弛函数，则d[c] = d[b]+w(b,c) = 3；
对边w(a,b)执行松弛函数，则d[b] = 1；
对边w(a,c)执行松弛函数，则d[c] = 6；
对边w(a,d)执行松弛函数，则d[d] = 10；

第二次迭代，有一条边起到了松弛的效果，直观的可以看出 d[c] = δ(a,c)，第二次迭代可以获得起点a到结点b、结点c的最短路径，路径为 P=<a,b,c>；

• 第三次迭代

对边w(c,d)执行松弛函数，则d[d] = d[c]+w(c,d) = 8；
对边w(b,c)执行松弛函数，则d[c] = 3；
对边w(a,b)执行松弛函数，则d[b] = 1；
对边w(a,c)执行松弛函数，则d[c] = 6；
对边w(a,d)执行松弛函数，则d[d] = 10；

第三次迭代，有一条边起到了松弛的效果，直观的可以看出 d[d] = δ(a,d)，第三次迭代可以获得起点a到结点b、结点c、结点d的最短路径，路径为 P=<a,b,c,d>；

1.3、迭代次数分析（反证法）

  详细过程，请查看：https://www.jianshu.com/p/b876fe9b2338

二、代码实现

  有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

2.1、方法一

  Bellman Ford + 类（模拟边）的代码实现，如下所示：

class Solution {
    private class Edge {
        int src;
        int dest;
        int cost;

        public Edge(int src, int dest, int cost) {
            this.src = src;
            this.dest = dest;
            this.cost = cost;
        }
    }

    int N = 110;
    int INF = 0x3f3f3f3f;
    int limit, src, dest;
    ArrayList<Edge> list = null;
    int[] distance = new int[N];

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        this.limit = k + 1;
        this.src = src;
        this.dest = dst;
        list = new ArrayList<Edge>();
        for (int[] flight : flights) {
            Edge edge = new Edge(flight[0], flight[1], flight[2]);
            list.add(edge);
        }
        int ans = dp();
        return ans > INF/2 ? -1 : ans;
    }

    public int dp() {
        Arrays.fill(distance, INF);
        distance[src] = 0;
        for (int i = 0; i < limit; i++) {
            int[] clone = distance.clone();
            for (Edge edge : list) {
                int src = edge.src, dest = edge.dest, cost = edge.cost;
                distance[dest] = Math.min(distance[dest], clone[src] + cost);
            }
        }
        return distance[dest];
    }
}

2.2、方法二

  直接利用数组 flights 的Bellman Ford算法，如下所示：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = 0x3f3f3f3f;
        int limit = k + 1;
        int[] distance = new int[n];
        Arrays.fill(distance, INF);
        distance[src] = 0;
        for (int i = 0; i < limit; i++) {
            int[] clone = distance.clone();
            for (int[] flight : flights) {
                int s = flight[0], d = flight[1], cost = flight[2];
                distance[d] = Math.min(distance[d], clone[s] + cost);
            }
        }
        return distance[dst] > INF / 2 ? -1 : distance[dst];
    }
}