昨天刚听老师讲了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;
	}
}