8月24日 每日一题 787. K 站中转内最便宜的航班经典最短路线图论题目: BFS,DP, Dijkstra, Bellman

admin管理员组

文章数量:1122850

8月24日 每日一题 787. K 站中转内最便宜的航班经典最短路线图论题目: BFS,DP, Dijkstra, Bellman

昨天刚听老师讲了3个小时的图与树的搜索策略,今天就碰到了这道每日一题. 打算花点时间用来熟悉一下各种方法.
K 站中转内最便宜的航班
这应该是把文章搬到CSDN的第一篇,之前的很多格式都出问题了,打算之后复习的时候改一下.

关于最短路的多种Java解法,这里存一个三叶公众号的链接:
宫水三叶最短路

这是一道「有限制」的最短路问题。

「限制最多经过不超过 kk 个点」等价于「限制最多不超过 k + 1k+1 条边」，而解决「有边数限制的最短路问题」是 SPFA 所不能取代 Bellman Ford 算法的经典应用之一（SPFA 能做，但不能直接做）。

Bellman Ford/SPFA 都是基于动态规划，其原始的状态定义为 f[i][k]f[i][k] 代表从起点到 ii 点，且经过最多 kk 条边的最短路径。这样的状态定义引导我们能够使用 Bellman Ford 来解决有边数限制的最短路问题。

同样多源汇最短路算法 Floyd 也是基于动态规划，其原始的三维状态定义为 f[i][j][k]f[i][j][k] 代表从点 ii 到点 jj，且经过的所有点编号不会超过 kk（即可使用点编号范围为 [1, k][1,k]）的最短路径。这样的状态定义引导我们能够使用 Floyd 求最小环或者求“重心点”（即删除该点后，最短路值会变大）。

首先是优化剪枝的python的BFS方法:

class Solution:def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:#图论题目#use bfsdic=defaultdict(list)min_cost=defaultdict(int)for edge in flights:dic[edge[0]].append((edge[1],edge[2]))min_cost[edge[0]]=float('INF')q,count,res=[(src,0)],0,-1while q and count<=k:new_q=[]for node in q:for nxt in dic[node[0]]:if nxt[0]==dst:if res==-1:res=nxt[1]+node[1]else:res=min(res,nxt[1]+node[1])continueif (res==-1 or nxt[1]+node[1]<res) and nxt[1]+node[1]<min_cost[nxt[0]]:min_cost[nxt[0]]=nxt[1]+node[1]new_q.append((nxt[0],nxt[1]+node[1]))q=new_qcount+=1return res

主要是用了两个hashtable来储存各种情况,然后按照层序bfs(记忆化)统计中转站点. 耗时一般:

接下来是用优先队列写的dijkstra题目:

class Solution:def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:#dijkstraINF = 10**9res = INFadjvex = defaultdict(list)for x,y,cost in flights:adjvex[x].append((y,cost))dist = [[INF]*(k+2) for _ in range(n)]dist[src][0] =0minheap=[]heapq.heappush(minheap,(0,src,0))while minheap:d,x,step = heapq.heappop(minheap)if x==dst:res=dbreakif step==k+1:continueif d> dist[x][step]:continuefor y,cost in adjvex[x]:if (dd := dist[x][step]+cost)<dist[y][step+1] :dist[y][step+1]=ddheapq.heappush(minheap,(dd,y,step+1))return res if res!=INF else -1

由于题目step的限制,所以我们不能像伪代码里面的一样,因为在一些情况下,对于node i的最短路径可能无法达到dst在step限制下的最短路径,所以要允许对一个step下的情况找到最短路径,而不是去找全局的最短路径.
说实话,写起来思路并没有bfs那么清晰还是要多练习. 实际上使用dijkstra的时候,大部分语言不会按照上面的伪代码写,一般是根据图的边和点的关系选择朴素dijkstra(n^2+m),n为node,m为edge.或者是选择堆优化dijistra(邻接表,mlogn+m).而我上面的就是堆优化的版本.

最后练一遍java的bfs题目:

class Solution {public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {int INF = (int) 1e9;int res = INF;Map<Integer, List<int[]>> adjvex = new HashMap<>();for (int[] f : flights) {int x = f[0], y = f[1], cost = f[2];adjvex.putIfAbsent(x, new ArrayList<int[]>());adjvex.get(x).add(new int[] { y, cost });}int[][] dist = new int[n][k + 2];for (int x = 0; x < n; x++) {Arrays.fill(dist[x], INF);}Queue<int[]> queue = new LinkedList<>();dist[src][0] = 0;queue.offer(new int[] { src, 0 });int step = 0;while (!queue.isEmpty()) {Queue<int[]> new_queue = new LinkedList<>();for (int[] node : queue) {int x = node[0], cost = node[1];if (x == dst) {res = Math.min(res, cost);continue;}if (step == k + 1) {continue;}if (cost > dist[x][step]) {continue;}for (int[] tmp : adjvex.getOrDefault(x, new ArrayList<int[]>())) {int y = tmp[0], nc = tmp[1];if (dist[x][step] + nc < dist[y][step + 1]) {dist[y][step + 1] = dist[x][step] + nc;new_queue.offer(new int[] { y, dist[y][step + 1] });}}}queue = new_queue;step += 1;}return res != INF ? res : -1;}
}

本文标签： 8月24日 每日一题 787 K 站中转内最便宜的航班经典最短路线图论题目 BFSDPDijkstrabellman