K站中转内最便宜的航班

2020-12-13


现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

 

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下
           0
         /  \
  100   /    \ 500
       /      \
      /  100   \
    1  -------- 2

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下
           0
         /  \
  100   /    \ 500
       /      \
      /  100   \
    1  -------- 2

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划

计算到各节点的最短距离

假设 pre[node] 是到经过 T 个节点到达目的节点 node 的最短距离，然后求解经过 T+1 个节点到达目的节点的最短距离。对于每一条连接城市 u 和 v，成本为 w的航线，更新后的最短距离为 dis[v] = min(dis[v], pre[u] + w)。

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[K + 1][n];
        for (int i = 0; i <= K; ++i) {
            Arrays.fill(dp[i], INF);
        }
        //初始化src可直达的班次
        for (int[] flight : flights) {
            if (flight[0] == src) {
                dp[0][flight[1]] = flight[2];
            }
        }
        //初始化数组中`dst == src`的行
        for (int i = 0; i <= K; i++) {
            dp[i][src] = 0;
        }

        for (int i = 1; i <= K; i++) {
            for (int[] flight : flights) {
                // 到flight[1]城市的cost=直达该城市的路线的cost和通过flight[0]+当前cost的最小值
                // 也就是选当前路线替换已有的路线和不选当前路线替换已有路线的最小值
                dp[i][flight[1]] = Math.min(dp[i][flight[1]], dp[i - 1][flight[0]] + flight[2]);
            }
        }
        return dp[K][dst] < INF ? dp[K][dst] : -1;
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] dist = new int[2][n];
        int INF = Integer.MAX_VALUE / 2;
        Arrays.fill(dist[0], INF);
        Arrays.fill(dist[1], INF);
        dist[0][src] = dist[1][src] = 0;

        for (int i = 0; i <= K; ++i)
            for (int[] edge: flights)//edge[1]是destination，edge[0]是当前节点的sorce，edge[2]是cost
                //i&1在i是奇数时为1，在i是偶数时为0，~对前面的结果取反
                dist[i&1][edge[1]] = Math.min(dist[i&1][edge[1]], dist[~i&1][edge[0]] + edge[2]);

        return dist[K&1][dst] < INF ? dist[K&1][dst] : -1;
    }
}

Dijkstra 算法

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] graph = new int[n][n];
        for (int[] flight: flights)
            graph[flight[0]][flight[1]] = flight[2];//赋值为从i到j的航班的cost

        Map<Integer, Integer> best = new HashMap();

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);//利用优先级队列维护花费最低的下一城市
        pq.offer(new int[]{0, 0, src});//第一个是cost，第二个是中转的数量k，第三个是source

        while (!pq.isEmpty()) {
            int[] info = pq.poll();
            int cost = info[0], k = info[1], place = info[2];
            if (k > K+1 || cost > best.getOrDefault(k * 1000 + place, Integer.MAX_VALUE))
                continue;
            if (place == dst)//如果当前节点终点，则返回当前的最小cost
                return cost;

            for (int nei = 0; nei < n; ++nei) 
                if (graph[place][nei] > 0) {//如果可达
                    int newcost = cost + graph[place][nei];
                    if (newcost < best.getOrDefault((k+1) * 1000 + nei, Integer.MAX_VALUE)) {
                        pq.offer(new int[]{newcost, k+1, nei});
                        best.put((k+1) * 1000 + nei, newcost);
                    }
            }
        }

        return -1;
    }
}

Dijkstra最短路径的实现代码


//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连    
//visit[i] == 0,代表未访问,visit[0] == -1代表已访问    
public int Dijkstra(int src, int dst, int[][] graph,int[] visit){
    //节点个数        
    int n = graph.length;        
    PriorityQueue<Node> pq = new PriorityQueue<>(new Node());        
    //将起点加入pq        
    pq.add(new Node(src, 0));        
    while (!pq.isEmpty()){            
        Node t = pq.poll();            
        //当前节点是终点，即可返回最短路径            
        if(t.node == dst)                
            return t.cost;            
        //t节点表示还未访问            
        if (visit[t.node]==0){                
            //将节点设置为已访问                
            visit[t.node] = -1;                
            //将当前节点相连且未访问的节点遍历                
            for (int i = 0; i < n; i++) {                    
                if (graph[t.node][i]!=0 && visit[i]==0) {                        
                    pq.add(new Node(i, t.cost + graph[t.node][i]));                    
                }                
            }            
        }        
    }        
    return -1;    
}    
//定义一个存储节点和离起点相应距离的数据结构    
class Node implements Comparator<Node> {        
    public int node;        
    public int cost;
             
    public Node(){}
     
    public Node(int node, int cost){            
        this.node = node;            
        this.cost = cost;        
    }        
    @Override        
    public int compare(Node node1, Node node2){            
        return node1.cost-node2.cost;       
    }    
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/k-zhan-zhong-zhuan-nei-zui-bian-yi-de-hang-ban-b-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。