2、BellMan-Ford算法

一、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+w(u,v)\]
则更新d[v]的值：

\[d[v]=d+w(u,v)\]
以是松懈函数的作用，就是判定是否颠末某个顶点，大概说颠末某条边，可以紧缩出发点到止境的路径权值。
1.2、BellMan-Ford算法中松懈函数的实验次数

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

  用d[d]表现出发点a到结点d的间隔，用δ(a,d)表现出发点a到结点d的最短路径权值，用p= 表现结点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)序次无影响；

• 第一次迭代
  

1. 对边w(a,b)执行松弛函数，则d[b] = d[a]+w(a,b) = 1；
2. 对边w(b,c)执行松弛函数，则d[c] = d[b]+w(b,c) = 3；
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)序次无影响；

• 第一次迭代
  

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

复制代码

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

• 第二次迭代
  

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

复制代码

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

• 第三次迭代
  

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

复制代码

第三次迭代，有一条边起到了松懈的效果，直观的可以看出 d[d] = δ(a,d)，第三次迭代可以得到出发点a到结点b、结点c、结点d的最短路径，路径为 P=；
1.3、迭代次数分析（反证法）

  具体过程，请检察：https://www.jianshu.com/p/b876fe9b2338
二、代码实现

  有 n 个都会通过一些航班毗连。给你一个数组 flights ，此中 flights = [fromi, toi, pricei] ，表现该航班都从都会 fromi 开始，以代价 pricei 抵达 toi。如今给定全部的都会和航班，以及出发都会 src 和目标地 dst，你的使命是找到出一条最多颠末 k 站中转的门路，使得从 src 到 dst 的 代价最自制 ，并返回该代价。 如果不存在如许的门路，则输出 -1。

2.1、方法一

  Bellman Ford + 类（模仿边）的代码实现，如下所示：
[code]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 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();        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