原题链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/
1、递归（超时）
代码：
2、动态规划
动态规划的思路就是求出所有从src走k个车站能到达的点，并记录最便宜票价。最后判断dst是否在这个集合里即可。
状态转移
代码：
3、Bellman-Ford算法
Bellman-Ford算法也是通过动态规划的思路，写的比第二种方法更优化了。这里顺便介绍一下Bellman-Ford算法。
Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。
Bellman-Ford 算法采用动态规划进行设计，实现的时间复杂度为 O(V*E)，其中 V 为顶点数量，E 为边的数量。Dijkstra 算法采用贪心算法进行设计，普通实现的时间复杂度为 O(V*V)，若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 O(E + VlogV)。
其思路为：
1、初始化时将起点s到各个顶点v的距离dist(s->v)赋值为∞，dist(s->s)赋值为0。
2、后续进行最多V-1次遍历操作(V为顶点个数),对所有的边进行松弛操作,所谓的松弛操作，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数，dist(b)代表起点s到达b点所需要花费的总数，weight(ab)代表边ab的权重，若存在: (dist(a) +weight(ab)) < dist(b)，则说明存在到b的更短的路径,s->…->a->b，更新b点的总花费为(dist(a) +weight(ab))，父节点为a。
3、遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路。
思路上与Dijkstra最大的不同是每次都是从源点s重新出发进行"松弛"更新操作，而Dijkstra则是从源点出发向外扩逐个处理相邻的节点，不会去重复处理节点，这里也可以看出Dijkstra效率相对更高点。
可用于解决以下问题：
1、从A出发是否存在到达各个节点的路径(计算出值即表示可以到达)；
2、从A出发到达各个节点最短路径(时间最少、费用最少等)；
3、图中是否存在负环路（求出各个最短路径之后还可以不断更新，即不断变小）。
对于这题来说，按照算法思路写即可，但是需要维护两个数组，一个是dp，一个是backup。backup是用于保存k-1的dp数组状态的，因为状态转移中，k时dp的更新是依赖k-1时的dp。
注意这题用Dijkstra算法并不是很好写，因为Dijkstra算法是在更新到某个结点之后，该结点的最短路径就确定了，就直接加入到数组中，下一次不会遍历这个结点了。但是这题因为有k的限制，所以存在需要回溯的情况。比如：
在k=1的条件下，如果用Dijkstra算法计算的话，当k=0时，将1加入集合中，权值为1；然后k=2时，会从1开始遍历，会将2加入集合中，权值为2；然后结果3不可达，而其实正确结果是3可达，权值为6。
引用链接：https://juejin.im/post/5b77fec1e51d4538cf53be68
评论留言