787. Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

Constraints:

1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst

Solution:

Dijkstra's Algorithm

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int result = Integer.MAX_VALUE;

        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : flights){
            int from = flight[0];
            int to = flight[1];
            int weight = flight[2];
            graph.putIfAbsent(from, new ArrayList<>());
            graph.get(from).add(new int[]{to, weight});
        }

        int[] stops = new int[n + 1];
        Arrays.fill(stops, Integer.MAX_VALUE);

        Set<Integer> visited = new HashSet<>();

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
        pq.offer(new int[]{src, 0, 0});
        while(!pq.isEmpty()){
                int[] cur = pq.poll();
                int curNode = cur[0];
                int curWeight = cur[1];
                int curStops = cur[2];

                if (curStops > stops[curNode] || curStops > k + 1){
                    continue;
                }

                if (curNode == dst){
                    return curWeight;
                }

                stops[curNode] = curStops;

                if (visited.contains(curNode)){
                    continue;
                }

                if (graph.containsKey(curNode)){
                    for(int[] nei : graph.get(curNode)){
                        int nextNode = nei[0];
                        int nextWeight = nei[1];
                        pq.offer(new int[]{nextNode, curWeight + nextWeight, curStops + 1});
                    }
                }

            }


        return -1;

    }

}

// TC: O(N∗Log(N))
// SC: O(N)

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Initialize the distance array
        int[][] dist = new int[n][k + 2]; // 4, 1+2 =3
        /** 
                0 1 2
            0   - - -
            1   - - -
            2   - - - 
            3   - - -
         */
         // 将数组中的每一行都填充为无穷大 (表示初始时所有城市的最小成本未知)
        for (int[] row : dist){
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        dist[src][0] = 0; // start: source city // 设置起点城市src在0次中转的成本为0
                /** 
                0 1 2
            0   0 0 -
            1   - - -
            2   - - - 
            3   - - -
         */
        // Iterate over the number of stops from 0 to k + 1
        // because allow k stops, so there will be k+ 1 edge
        // 从1次中转开始循环, 到(k+1)次中转为止
        for (int stops = 1; stops <= k + 1; stops++){
            // 在每一轮中转开始时, 将上一轮的成本拷贝到当前轮次
            for (int i = 0; i < n; i++){
                dist[i][stops] = dist[i][stops - 1];
                // dist[0][1] = dist[0][0] = 0
                // dist[1][1] = dist[1][0] = -
            }

            // 遍历所有的航班信息
            for (int[] flight : flights){
                // [0, 1, 100]
                int from = flight[0];//0
                int to = flight[1];//1
                int price = flight[2]; // 100
                if (dist[from][stops - 1] != Integer.MAX_VALUE){
                    // dist[0][0] = 0
                    dist[to][stops] = Math.min(dist[to][stops], dist[from][stops - 1] + price);
                    // dist[1][1] = Math.min(dist[1][1], dist[0][1] + 100);
                    // dist[1][1] = Math.min(-, 100)
                    // dist[1][1] = 100
                }
            }
        }

        // Find the minimum cost to reach dst with up to k + 1 stops
        int minCost = Integer.MAX_VALUE;
        for (int stops = 0; stops <= k + 1; stops++){
            minCost = Math.min(minCost, dist[dst][stops]);
        }

        return minCost == Integer.MAX_VALUE ? -1 : minCost;
    }
}

int[][] dist = new int[n][k + 2];

n: 数组的行数等于城市的数量, 每一行代表一个城市

k+2 : 需要考虑从0次中转到k+1次中转的情况

787. Cheapest Flights Within K Stops

Dijkstra's Algorithm

Bellman Ford