# Dijkstra

#### [787. Cheapest Flights Within K Stops](https://leetcode.com/problems/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)* 

```java
    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](https://leetcode.com/problems/the-maze-ii/)

```java
    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

```java
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](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/)

#### [1548. The Most Similar Path in a Graph](https://leetcode.com/problems/the-most-similar-path-in-a-graph/)

```java
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](https://leetcode.com/problems/path-with-minimum-effort/)

```java
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](https://leetcode.com/problems/path-with-maximum-probability/)

```java
 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](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/)

```java
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;
}
```

[3341. Find Minimum Time to Reach Last Room I](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/)

```java
class Solution {

    private static final int INF = Integer.MAX_VALUE;

    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length, m = moveTime[0].length;
        int[][] d = new int[n][m];
        boolean[][] v = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(d[i], INF);
        }

        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        d[0][0] = 0;
        PriorityQueue<State> q = new PriorityQueue<>();
        q.offer(new State(0, 0, 0));

        while (!q.isEmpty()) {
            State s = q.poll();
            if (v[s.x][s.y]) {
                continue;
            }
            v[s.x][s.y] = true;
            for (int[] dir : dirs) {
                int nx = s.x + dir[0];
                int ny = s.y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                int dist = Math.max(d[s.x][s.y], moveTime[nx][ny]) + 1;
                if (d[nx][ny] > dist) {
                    d[nx][ny] = dist;
                    q.offer(new State(nx, ny, dist));
                }
            }
        }
        return d[n - 1][m - 1];
    }

    static class State implements Comparable<State> {

        int x, y, dis;

        State(int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }

        @Override
        public int compareTo(State other) {
            return Integer.compare(this.dis, other.dis);
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/graph/dijkstra.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.