昨天刚听老师讲了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 bfs
dic=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,-1
while 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])
continue
if (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_q
count+=1
return res
主要是用了两个hashtable来储存各种情况,然后按照层序bfs(记忆化)统计中转站点. 耗时一般:
接下来是用优先队列写的dijkstra题目:
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
#dijkstra
INF = 10**9
res = INF
adjvex = defaultdict(list)
for x,y,cost in flights:
adjvex[x].append((y,cost))
dist = [[INF]*(k+2) for _ in range(n)]
dist[src][0] =0
minheap=[]
heapq.heappush(minheap,(0,src,0))
while minheap:
d,x,step = heapq.heappop(minheap)
if x==dst:
res=d
break
if step==k+1:
continue
if d> dist[x][step]:
continue
for y,cost in adjvex[x]:
if (dd := dist[x][step]+cost)<dist[y][step+1] :
dist[y][step+1]=dd
heapq.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;
}
}