[LeetCode]Cheapest Flights Within K Stops

带权图最短路径的问题，区别是在于这道题限定了只经过K个节点的最短路径，我们在这篇文章总结过最短路径的各种算法，我们依然会采用类似的思路，只是需要做一些修改。Dijkstra依然是可行的，但是我们要加一个限制条件，那就是经过的节点数不超过K。算法依然是类似的，但是这里我们注意我们是允许优先队列上的节点被展开多次的，例如下图：

假设我们要找0到3的最短路径，并且只允许经过一个中间节点。我们第一次展开2节点的时候，是通过0->1->2这条长度为2的路径，但是此时我们不会继续了，因为已经经过了一个中间节点。第二次我们展开的时候已经走过了长度为5的路径，这个时候我们还可以继续，所以最后会找到0->2->3这条长度为6的路径，保证最多只经过一个中间节点的最短路径。
换句话说，从source到某个节点v的最短路径(K或更少个中间节点)，并不一定在source到target的最短路径上(K或更少个中间节点)，所以我们要允许节点的多次展开，时间复杂度O(E * log E)，代码如下：

另一个思路就是Bellman Ford，我们知道Bellman Ford对所有边进行N - 1次relax可以保证我们找到最多包含了N - 1条边的从源节点开始的最短路径。但是这并不代表我们进行K次relax就可以找到最多包含K条边的最短路径。比如假设图就是一维的0-1-2-3-4-5这样的，扫边的时候如果正好是从左向右，那么只要1次我们就可以找到包含5条边的从0开始的最短路径；反之如果我们是从右往左扫的边，我们则需要5次才能找到。这也就是说，对所有边进行了K次relax，我们找到的是至少包含K条边的最短路径，和题目中要求的相反，所以我们需要做一些改变。如果我们用dp[i][v]表示经过i条边从源节点到达v节点的最短路径，那么每一次relax的时候，我们就可以保证：

• dp[i][v] = min(dp[i][v], dp[i - 1][u] + w(u, v)), 其中u是v的邻节点，w(u, v)是连接u和v的边的权值

换句话说这也就是递推方程。这样可以保证每一次我们对所有边relax，可以找到的从源节点到所有节点的最短路径所经过的边数加一。时间复杂度O(V * E)，代码如下：