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]的值所以松弛函数的作用就是判断是否经过某个顶点或者说经过某条边可以缩短起点到终点的路径权值。1.2、BellMan-Ford算法中松弛函数的执行次数现有所有结点a~d如下图所示用d[d]表示起点a到结点d的距离用δ(a,d)表示起点a到结点d的最短路径权值用pa,...,d 表示结点a到结点d的路径初始情况d[a]0d[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的最短路径路径为 Pa,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的最短路径路径为 Pa,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的最短路径路径为 Pa,b,c,d1.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; ArrayListEdge 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 ArrayListEdge(); 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]; } }时间复杂度共进行 k 1次迭代每次迭代备份数组复杂度为 O(n)n为所有结点的数量然后遍历所有的边进行松弛操作复杂度为 O(m)m为所有边的数量。整体复杂度为 O(k * (n m))空间复杂度O(n m)n为所有结点的数量m为所有边的数量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]; } }时间复杂度共进行 k 1次迭代每次迭代备份数组复杂度为 O(n)n为所有结点的数量然后遍历所有的边进行松弛操作复杂度为 O(m)m为所有边的数量。整体复杂度为 O(k * (n m))空间复杂度O(n m)n为所有结点的数量m为所有边的数量