It's the old rule. 1102 743 1129 1514 1631 787. Among them, 787 is more complex. The last exercise is recommended.

There is also 1334 (this problem is solved by floyd algorithm, because it is not the shortest single source, but the shortest multi-source. I think it is too textbook. Reciting floyd is a second kill)

There are still a lot of problems related to the deformation of Dijsktra algorithm in Leetcode. I hate reciting the algorithm, because I find that no matter how I recite it, I will still forget when the interview is nervous, because during the interview, I will subconsciously believe what I recite rather than what I understand. If I recite it wrong, I will kneel. You may ask Dijkstra if you understand the algorithm. It's a very pediatric algorithm. I agree with that. But I personally prefer to use BFS, a more general algorithm to solve problems rather than a specific algorithm. If you want to recite, BFS is better than Dijkstra.

As like as two peas, the single source shortest BFS basic framework is almost exactly the same. One record array and one Queue do BFS (PriorityQueue can speed up the algorithm).

Let's start with a simple example of 1631

class Step { //This class is used to record the current state
    int x;
    int y;
    int effort;
    public Step(int _x, int _y, int _effort) {
        x = _x;
        y = _y;
        effort = _effort;
    }
}
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        int[][] miniEffort = new int[m][n]; //Here is our record array
        for(int i = 0; i < m; i++) { //Initialization of record array
            for(int j = 0; j < n; j++) {
                miniEffort[i][j] = Integer.MAX_VALUE;
            }
        }
        miniEffort[0][0] = 0;
        int[][] moves = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        PriorityQueue<Step> queue = new PriorityQueue<>((s1, s2) -> s1.effort - s2.effort); //This is the Queue where our BFS stores records
        queue.add(new Step(0, 0, 0));
        while(queue.size() > 0) {
            Step cur = queue.poll();
            for(int[] move : moves) {
                int nextx = cur.x + move[0], nexty = cur.y + move[1];
                if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
                    int diff = Math.abs(heights[nextx][nexty] - heights[cur.x][cur.y]);
                    int nextDiff = Math.max(diff, cur.effort);
                    if (nextDiff < miniEffort[nextx][nexty]) {
                        miniEffort[nextx][nexty] = nextDiff;
                        queue.add(new Step(nextx, nexty, nextDiff));
                    }
                }
            }
        }
        return miniEffort[m - 1][n - 1];
    }
}

In this question, it stipulates that A route's # effect # is the # maximum absolute difference # in heights between two conservative cells of the route Then the final goal is the minimum effect of the lowest point on the far right. At the beginning, I thought about dynamic planning, and then found that four directions of southeast and northwest are OK, which obviously won't work. So I started to do routine. Since the final result is a single point, I'll use this BFS method.

1. The record array is used to store the minimum effort to reach each point in the current search (initially set to positive infinity).

2. For the state of reaching a point, we need to record the coordinates of the current point and the minimum effort to reach the current point no matter how we arrive.

3. When we start the next step, compare the minimum effect caused by the next step with the minimum effect in the record array. If it is smaller than that in the record array, it means that we don't know how to find a better path and bring better benefits, then this path should continue to try. If it is the same or greater than, we can guarantee that taking this road will not bring better benefits at least, then this road can be interrupted and there is no need to try again (this is also the most important link for us to avoid repeated search and go back to the original road). At the same time, when we continue to try, we should update the value of the record array, because we have found a better path and brought higher benefits.

4. Consider the convergence of search. Because we add the judgment conditions of the search, the value in the record array will always be smaller and smaller, and the final answer is OK. Therefore, when this value is the same as the final answer, the search process will end and will not fall into an infinite loop.

In these four steps, you can put forward the idea of general and practice with the question numbers I listed, and you will soon master it. I call this BFS lazy practice, and the routine is too obvious. The reason for using PriorityQueue is to let the paths that may lead to the optimal results be searched first, so that we can avoid searching the paths that are logically impossible to achieve the optimal results.

The following Po gives the code of 787. This problem is really difficult, but it can be solved by my method, which means you have mastered the key points of this kind of BFS.

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        if(src == dst) {
            return 0;
        }
        HashMap<Integer, HashMap<Integer, Integer>> flightsInfo = new HashMap<>();
        for(int[] flight : flights) {
            if (flightsInfo.get(flight[0]) == null) {
                flightsInfo.put(flight[0], new HashMap<>());
            }
            flightsInfo.get(flight[0]).put(flight[1], flight[2]);
        }
        if (K == 0) {
            if (flightsInfo.get(src) != null) {
                return flightsInfo.get(src).getOrDefault(dst, -1);
            }
            return -1;
        }
        int[][2] cheapest = new int[n][2];
        PriorityQueue<int[]> queue = new PriorityQueue<>((t1, t2) -> t1[1] - t2[1]);
        queue.add(new int[]{src, 0, 0});
        int ret = Integer.MAX_VALUE;
        while(queue.size() > 0) {
            int[] cur = queue.poll();
            int node = cur[0], cost = cur[1], stops = cur[2];
            HashMap<Integer, Integer> neighbors = flightsInfo.get(node);
            if (neighbors == null) {
                continue;
            }
            if (cheapest[node][0] != 0 && node != src && cost > cheapest[node][0]) {
                continue;
            }
            for(Map.Entry<Integer, Integer> neighbor : neighbors.entrySet()) {
                int nextCity = neighbor.getKey(), nextCost = cost + neighbor.getValue();
                int nextStops = stops + 1;
                if (nextCity == dst) {
                    ret = Math.min(ret, nextCost);
                    continue;
                }
                if (nextStops > K) {
                    continue;
                }
                if (cheapest[nextCity][0]== 0 || nextCost < cheapest[nextCity][0] || nextCost == cheapest[nextCit]) {
                    queue.add(new int[]{nextCity, nextCost, nextStops});
                    cheapest[nextCity] = nextCost;
                }
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;

My method may not be the fastest, but I think it is the most suitable for the interview, because the routine is obvious. When you are proficient, you will copy it like a fool. And the time complexity analysis is particularly easy, that is, how many times does each point need to be compared with the value in the record array at most × Number of logical points.