> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/graph/dijkstra.md).

# 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);
        }
    }
}
```