Dijkstra

787. Cheapest Flights Within K Stops

Use Djikstra algorithm, store current city, stops from start and price from start in the priority queue, and rank by price from start. Pop the stop with lowest price, and find the next stops, stops from start += 1, and "price from start" + next price. Until reach destination, otherwise return -1.

T: O((V + E)*logV) S: O(V^2)

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int[] flight : flights) {
            map.putIfAbsent(flight[0], new HashMap<>());
            map.get(flight[0]).put(flight[1], flight[2]);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<>(){
            public int compare(int[] a, int[] b) {
                return a[2] - b[2];
            }
        });
        pq.offer(new int[]{src, 0, 0});
        while (!pq.isEmpty()) {
            int[] curt = pq.poll();
            int price = curt[2];
            int city = curt[0];
            int stop = curt[1];
            if (city == dst) return price;
            if (stop < K + 1) {
                Map<Integer, Integer> nexts = map.getOrDefault(
                        city, new HashMap<>());
                for (int next : nexts.keySet()) {
                    pq.offer(new int[]{next, stop + 1, price + nexts.get(next)});
                }
            }
        }
        return -1;
    }

505. The Maze II

    int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;
        PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return o1.dist - o2.dist;
            }
        });
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i], Integer.MAX_VALUE);
        }
        Point startPoint = new Point(start[0], start[1], 0);
        memo[start[0]][start[1]] = 0;
        pq.offer(startPoint);
        while (!pq.isEmpty()) {
            Point curt = pq.poll();
            for (int[] d : dir) {
                int nx = curt.x, ny = curt.y;
                int dist = curt.dist;
                while (isValid(maze, nx + d[0], ny + d[1])) {
                    nx += d[0];
                    ny += d[1];
                    dist++;
                }
                if (dist >= memo[nx][ny]) continue;
                memo[nx][ny] = Math.min(memo[nx][ny], dist);
                if (nx == destination[0] && ny == destination[1]) return dist;
                Point next = new Point(nx, ny, dist);
                pq.offer(next);
            }
        }
        return -1;
    }

    private boolean isValid(int[][] m, int x, int y) {
        return x >= 0 && y >= 0 && x < m.length && y < m[0].length && m[x][y] != 1;
    }

    class Point {
        int x, y;
        int dist;
        Point(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.dist = d;
        }
    }

499. The Maze III

class Point {
    private int row, col, dist;
    private String path;
    Point(int r, int c, int d, String p) {
        row = r;
        col = c;
        dist = d;
        path = p;
    }
}

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    char[] turns = {'d', 'u', 'r', 'l'};
    int m = maze.length, n = maze[0].length;
    boolean[][] marked = new boolean[m][n];
    PriorityQueue<point> minheap = new PriorityQueue<>(new Comparator<point>() {
        @Override
        public int compare(point o1, point o2) {
            if (o1.dist == o2.dist) return o1.path.compareTo(o2.path);
            else return o1.dist - o2.dist;
        }
    });
    minheap.add(new Point(ball[0], ball[1], 0, ""));
    while (!minheap.isEmpty()) {
        point cur = minheap.poll();
        int row = cur.row, col = cur.col;
        if (row == hole[0] && col == hole[1]) return cur.path;
        if (marked[row][col]) continue;
        marked[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int r = row, c = col, dist = cur.dist;
            while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0 && (r != hole[0] || c != hole[1])) {
                r += dirs[i][0];
                c += dirs[i][1];
                dist++;
            }
            if (r != hole[0] || c != hole[1]) {
                r -= dirs[i][0];
                c -= dirs[i][1];
                dist--;
            }
            if (!marked[r][c]) {
                minheap.add(new Point(r, c, dist, cur.path + turns[i]));
            }
        }
    }
    return "impossible";
}

1368. Minimum Cost to Make at Least One Valid Path in a Grid

1548. The Most Similar Path in a Graph

public List<Integer> mostSimilar(int n, int[][] roads, String[] names, String[] targetPath) {
    // build the graph
    List<Integer>[] g = new ArrayList[n];
    for(int[] r: roads) {
        int a = r[0]; int b = r[1];
        if (g[a] == null) g[a] = new ArrayList<>();
        if (g[b] == null) g[b] = new ArrayList<>();
        g[a].add(b);
        g[b].add(a);
    }
    
    int m = targetPath.length;
    int[][] path = new int[n][m]; // record the path. path[i][j] stores the previous city 
                                  // for city i at position j
    int[][] dist = new int[n][m]; // dist[i][j] is the min edit distance for city i at position j
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->{
        int da = dist[a[0]][a[1]];
        int db = dist[b[0]][b[1]];
        if (da == db) return b[1] - a[1];
        return da - db;
    });
    
    for(int i = 0; i < n; i++) {
        dist[i][0] = targetPath[0].equals(names[i]) ? 0 : 1;
        pq.offer(new int[]{i, 0});
        for(int j = 1; j < m; j++) dist[i][j] = Integer.MAX_VALUE;
    }
    
    int min = Integer.MAX_VALUE;
    while(!pq.isEmpty()) {
        int[] a = pq.poll();
        int c = a[0]; int p = a[1];
        int d = dist[c][p];
        if (p == m-1) break;
        for(int b: g[a[0]]) {
            int dd = d + (targetPath[p+1].equals(names[b]) ? 0 : 1);
            if (dd < dist[b][p+1]) {
                dist[b][p+1] = dd;
                pq.offer(new int[]{b, p+1});
                path[b][p+1] = c;
            }
        }
    }
    
    int last = 0;
    for(int i = 1; i < n; i++) {
        if (dist[i][m-1] < dist[last][m-1]) last = i;
    }
    
    LinkedList<Integer> ans = new LinkedList<>();
    for(int i = m-1; i >= 0; i--) {
        ans.push(last);
        last = path[last][i];
    }
    return ans;
}

1631. Path With Minimum Effort

int[] DIR = new int[]{0, 1, 0, -1, 0};
public int minimumEffortPath(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    int[][] dist = new int[m][n];
    for (int i = 0; i < m; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
    
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    minHeap.offer(new int[]{0, 0, 0}); // distance, row, col
    while (!minHeap.isEmpty()) {
        int[] top = minHeap.poll();
        int d = top[0], r = top[1], c = top[2];
        if (d > dist[r][c]) continue;
        if (r == m - 1 && c == n - 1) return d; // Reach to bottom right
        for (int i = 0; i < 4; i++) {
            int nr = r + DIR[i], nc = c + DIR[i + 1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int newDist = Math.max(d, Math.abs(heights[nr][nc] - heights[r][c]));
                if (dist[nr][nc] > newDist) {
                    dist[nr][nc] = newDist;
                    minHeap.offer(new int[]{dist[nr][nc], nr, nc});
                }
            }
        }
    }
    return 0; // Unreachable code, Java require to return interger value.
}

1514. Path with Maximum Probability

 public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    Map<Integer, List<int[]>> g = new HashMap<>();
    for (int i = 0; i < edges.length; ++i) {
        int a = edges[i][0], b = edges[i][1];
        g.computeIfAbsent(a, l -> new ArrayList<>()).add(new int[]{b, i});    
        g.computeIfAbsent(b, l -> new ArrayList<>()).add(new int[]{a, i});    
    }
    double[] p = new double[n];
    p[start] = 1d;
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingDouble(i -> -p[i]));
    pq.offer(start);
    while (!pq.isEmpty()) {
        int cur = pq.poll();
        if (cur == end) {
            return p[end];
        }
        for (int[] a : g.getOrDefault(cur, Collections.emptyList())) {
            int neighbor = a[0], index = a[1];
            if (p[cur] * succProb[index] > p[neighbor]) {
                p[neighbor] = p[cur] * succProb[index];
                pq.offer(neighbor);
            }
        }
    }
    return 0d;
}

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    Map<Integer, Map<Integer, Integer>> g = new HashMap<>();
    for (int i = 0; i < n; i++) {
        g.put(i, new HashMap<>());
    }
    for (int[] e : edges) {
        g.get(e[0]).put(e[1], e[2]);
        g.get(e[1]).put(e[0], e[2]);
    }
    int min = n + 1;
    int res = -1;
    for (int i = 0; i < n; i++) {
        Queue<int[]> q = new PriorityQueue<>((a, b)->(b[1] - a[1]));
        q.add(new int[]{i, distanceThreshold});
        Set<Integer> visited = new HashSet<>();
        int count = 0;
        while (!q.isEmpty()) {
            int[] city = q.poll();
            if (!visited.contains(city[0])) {
                visited.add(city[0]);
                count++;
            } else {
                continue;
            }
            Map<Integer, Integer> m = g.get(city[0]);
            for (int neighbor : m.keySet()) {
                if (!visited.contains(neighbor) && city[1] >= m.get(neighbor)) {
                    q.add(new int[]{neighbor, city[1] - m.get(neighbor)});
                }
            }
        }
        if (count - 1 <= min) {
            min = count - 1;
            res = i;
        }
    }
    return res;
}