Shortest Path Problem

迪杰斯特拉

解析

  1. 开一个dis数组，记录从给定点x到其他点的最短距离，初始化为max，；开一个visited数组，记录顶点是否被访问过
  2. 将x的dis初始为0
  3. 开始遍历，首先找到未被访问且距离x最短的顶点y，将y的visited赋值true
  4. 更新的dis中顶点z的距离：未被访问且 z与x的距离大于 x到y + y到z的距离

743. 网络延迟时间

方法一：迪杰斯特拉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
final int inf = Integer.MAX_VALUE / 2;
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] graph = new int[n + 1][n + 1];
        for (int[] g : graph)
            Arrays.fill(g, inf);
        for (int[] time : times) {
            int from = time[0], to = time[1], weight = time[2];
            graph[from][to] = weight;
        }
        int[] dist = dijkstra(graph, n, k);
        int res = 0;
        for (int x : dist) {
            if (x == inf)
                return -1;
            res = Math.max(res, x);
        }
        for (int d : dist)
            System.out.print(d + ", ");
        System.out.println();
        return res;
    }

    public int[] dijkstra(int[][] graph, int n, int from) {
        int[] dist = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            if (i != from)
                dist[i] = inf;
        // 不要把visited[from]初始为true，dist[from] = 0，会在下面的for循环中被第一个选到
        boolean[] visited = new boolean[n + 1];
        for (int i = 0; i < n; ++i) { // 每遍历一次将一个顶点visit赋值true，需要遍历n次
            int minIndex = -1, minDist = inf;
            for (int j = 1; j <= n; ++j) {
                if (!visited[j] && dist[j] < minDist) {
                    minIndex = j;
                    minDist = dist[j];
                }
            }
            if (minIndex == -1) // 如果有节点非连通，则返回
                return dist;
            visited[minIndex] = true;
            for (int j = 1; j <= n; ++j)
                if (!visited[j] && dist[j] > graph[minIndex][j] + minDist)
                    dist[j] = graph[minIndex][j] + minDist;
        }
        return dist;
    }
}

方法二：堆优化dijkstra

我们还可以使用一个小根堆来寻找「未确定节点」中与起点距离最近的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    final int inf = Integer.MAX_VALUE / 2;
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] graph = new int[n + 1][n + 1];
        for (int[] g : graph)
            Arrays.fill(g, inf);
        for (int[] time : times) {
            int from = time[0], to = time[1], weight = time[2];
            graph[from][to] = weight;
        }
        int[] dist = dijkstra(graph, n, k);
        int res = 0;
        for (int x : dist) {
            if (x == inf)
                return -1;
            res = Math.max(res, x);
        }
        return res;
    }

    public int[] dijkstra(int[][] graph, int n, int from) {
        int[] dist = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            if (i != from)
                dist[i] = inf;
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
        queue.offer(new int[]{from, 0});
       while (!queue.isEmpty()) {
           int[] arr = queue.poll();
           int node = arr[0], disToFrom = arr[1];
           if (visited[node])
               continue;
           visited[node] = true;
           for (int i = 1; i <= n; ++i) {
               // graph[node][i] < inf表示node与i有边
               if (graph[node][i] < inf && dist[i] > disToFrom + graph[node][i]) {
                   dist[i] = disToFrom + graph[node][i];
                   queue.offer(new int[]{i, dist[i]});
               }
           }
       }
        return dist;
    }
}

322. 零钱兑换

方法一：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int coinChange(int[] coins, int amount) {
        Queue<int[]> queue = new LinkedList<>();
        // 第一个元素表示已经凑成的钱(距离)，第二个元素表示使用的硬币数(步数)
        queue.offer(new int[]{0 , 0});
        boolean[] visited = new boolean[amount + 1];
        visited[0] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int sum = node[0], num = node[1];
            if (sum == amount)
                return num;
            for (int coin : coins) {
                if (coin > amount - sum || visited[sum + coin])
                    continue;
                queue.offer(new int[]{sum + coin, num + 1});
                visited[sum + coin] = true;
            }
        }
        return -1;
    }
}

45. 跳跃游戏 II

方法一：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int jump(int[] nums) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        boolean[] visited = new boolean[nums.length];
        visited[0]= true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int pos = node[0], step = node[1];
            if (pos == nums.length - 1)
                return step;
            for (int i = 1; i <= nums[pos]; ++i)  {
                if (pos + i >= nums.length || visited[pos + i])
                    continue;
                queue.offer(new int[]{pos + i, step + 1});
                visited[pos + i] = true;
            }
        }
        return -1;
    }
}

542. 01 矩阵

方法一：BFS

  1. queue三元组，分别为横坐标i，纵坐标j，mat[i][j]距离0的距离
  2. 将所有0加入队列，并标记visited
  3. BFS搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] res =  new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j, 0}); // x, y, distance
                    visited[i][j] = true;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int i = node[0], j = node[1], dist = node[2];
            for (int[] dir :dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col, m, n) && !visited[row][col]) {
                    res[row][col] = dist + 1;
                    queue.offer(new int[]{row, col, dist + 1});
                    visited[row][col] = true;
                }
            }
        }
        return res;
    }
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >=0 && i < m && j < n;
    }
}

773. 滑动谜题

1334. 阈值距离内邻居最少的城市

不能用BFS做，这是求多源最短路径

方法一：弗洛伊德

  1. dp[i][j]表示i到j的最短距离
  2. 枚举所有中间节点k，如果i经过中间节点k再到达j比i直接到达j更短，那么将dp[i][j]赋值为dp[i][k] + dp[k][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dp = buildGraph(n, edges);
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
        int minNum = 100000, minIndex = -1;
        for (int i = 0; i < n; ++i) {
            int neighborsNum = 0;
            for (int j = 0; j < n; ++j)
                if (i!= j && dp[i][j] <= distanceThreshold)
                    ++neighborsNum;
            if (neighborsNum <= minNum) {
                minNum = neighborsNum;
                minIndex = i;
            }
        }
        return minIndex;
    }

    private int[][] buildGraph(int n, int[][] edges) {
        int[][] graph = new int[n][n];
        for (int[] row : graph)
            Arrays.fill(row, 100000);
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            graph[from][to] = graph[to][from] = weight;
        }
        return graph;
    }
}

剑指 Offer II 107. 矩阵中的距离

方法一：BFS

BFS可以确保从0到非0元素的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        int[][] dist = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; ++i) 
            for (int j = 0; j < n; ++j)
                if (mat[i][j] == 0)
                    queue.offer(new int[]{i, j});
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && mat[row][col] != 0 && dist[row][col] == 0) {
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        return dist;
    }

    int m, n;
    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
    
}

剑指 Offer II 108. 单词演变

方法一：单向BFS

不能使用queue2.clear()，因为queue1是指向queue2内存空间的

1
2
3
4
5
 if (queue1.isEmpty()) {
    ++length;
    queue1 = queue2;
    queue2 = new LinkedList<>();
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        Queue<String> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        queue1.offer(beginWord);
        int length = 1;
        while (!queue1.isEmpty()) {
            String node = queue1.poll();
            if (node.equals(endWord))
                return length;
            List<String> neibors = getNeibors(node);
            for (String next : neibors) {
                if (set.contains(next)) {
                    queue2.offer(next);
                    // 通过bfs最先遍历到的节点，距离初始节点的距离一定是最短的
                    set.remove(next);
                }
            }
            if (queue1.isEmpty()) {
                ++length;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return 0;
    }

    private List<String> getNeibors(String node) {
        List<String> neibors = new LinkedList<>();
        char[] chs = node.toCharArray();
        for (int i = 0; i < chs.length; ++i) {
            char ch = chs[i];
            for (char j = 'a'; j <= 'z'; ++j) {
                if (ch != j) {
                    chs[i] = j;
                    neibors.add(new String(chs));
                }
            }
            chs[i] = ch;
        }
        return neibors;
    }
}

方法二：双向BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> notVisited = new HashSet<>(wordList);
        if (!notVisited.contains(endWord))
            return 0;
        Set<String> set1 = new HashSet<>(), set2 = new HashSet<>();
        set1.add(beginWord);
        set2.add(endWord);
        notVisited.remove(endWord);
        int length = 2;
        while (!set1.isEmpty() && !set2.isEmpty()) {
            if (set1.size() > set2.size())  {
                Set<String> temp = set1;
                set1 = set2;
                set2 = temp;
            }
            Set<String> set3 = new HashSet<>();
            for (String word : set1) {
                List<String> neibors = getNeibors(word);
                for (String next : neibors) {
                    if (set2.contains(next))
                        return length;
                    if (notVisited.contains(next)) {
                        set3.add(next);
                        notVisited.remove(next);
                    }
                }
            }
            ++length;
            set1 = set3;
            set3 = new HashSet<>();
        }
        return 0;
    }

    private List<String> getNeibors(String node) {
        List<String> neibors = new LinkedList<>();
        char[] chs = node.toCharArray();
        for (int i = 0; i < chs.length; ++i) {
            char ch = chs[i];
            for (char j = 'a'; j <= 'z'; ++j) {
                if (ch != j) {
                    chs[i] = j;
                    neibors.add(new String(chs));
                }
            }
            chs[i] = ch;
        }
        return neibors;
    }
}

剑指 Offer II 109. 开密码锁

方法一：单向BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> notAchievable = new HashSet<>(Arrays.asList(deadends));
        if (notAchievable.contains("0000"))
            return -1;
        Queue<String> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        queue1.offer("0000");
        Set<String> visited = new HashSet<>();
        int length = 0;
        while (!queue1.isEmpty()) {
            String node = queue1.poll();
            if (node.equals(target))
                return length;
            List<String> neibors = getNeibors(node, notAchievable);
            for (String next : neibors) {
                if (visited.contains(next))
                    continue;
                visited.add(next);
                queue2.offer(next);
            }
            if (queue1.isEmpty()) {
                ++length;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return -1;
    }

    private List<String> getNeibors(String node, Set<String> notAchievable) {
        List<String> neibors = new LinkedList<>();
        char[] chs = node.toCharArray();
        String pre, next;
        for (int i = 0; i < 4; ++i) {
            char ch = chs[i];
            if (ch == '0') {
                chs[i] = '1';
                next = new String(chs);
                if (!notAchievable.contains(next))
                    neibors.add(next);
                chs[i] = '9';
                pre = new String(chs);
                if (!notAchievable.contains(pre))
                    neibors.add(new String(chs));
            }
            else if (ch == '9') {
                chs[i] = '0';
                next = new String(chs);
                if (!notAchievable.contains(next))
                    neibors.add(next);
                chs[i] = '8';
                pre = new String(chs);
                if (!notAchievable.contains(pre))
                    neibors.add(pre);
            }
            else {
                chs[i] = (char) (ch + 1);
                next = new String(chs);
                if (!notAchievable.contains(next))
                    neibors.add(next);
                chs[i] = (char) (ch - 1);
                pre = new String(chs);
                if (!notAchievable.contains(pre))
                    neibors.add(pre);
            }
            chs[i] = ch;
        }
        return neibors;
    }
}

6951. 找出最安全路径

方法一：多源BFS

二分做右端点的初始

1
int l = 0, r = Math.min(dist[0][0], dist[n - 1][n - 1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                grid[i][j] = g.get(i).get(j);
        int[][] dist = new int[n][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }

        
        int l = 0, r = Math.min(dist[0][0], dist[n - 1][n - 1]);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, dist))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;

    }

    private boolean check(int limit, int[][] dist) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && !visited[row][col] && dist[row][col] >= limit) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        return visited[n - 1][n - 1];
    }


    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
}

在check中判断初始位置，r = 2 * n - 1 (大一点也没关系)

1
2
if (dist[0][0] < limit)
    return false;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                grid[i][j] = g.get(i).get(j);

        int[][] dist = new int[n][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }

        
        int l = 0, r = 2 * n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, dist))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;

    }

    private boolean check(int limit, int[][] dist) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        if (dist[0][0] < limit)
            return false;
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && !visited[row][col] && dist[row][col] >= limit) {
                    visited[row][col] = true;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        return visited[n - 1][n - 1];
    }


    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
}

check使用DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        dist = new int[n][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = g.get(i).get(j);
                dist[i][j] = -1;
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }
        // bfs
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] dir : dirs) {
                int row = node[0] + dir[0], col = node[1] + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    queue.offer(new int[]{row, col});
                    dist[row][col] = dist[node[0]][node[1]] + 1;
                }
            }
        }
        int l = 0, r = (n - 1) << 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }

    private boolean check(int minDist) {
        if (dist[0][0] < minDist)
            return false;
        boolean[][] visited = new boolean[n][n];
        return dfs(0, 0, minDist, visited);
    }

    private boolean dfs(int i, int j, int minDist, boolean[][] visited) {
        if (i == n -1 && j == n - 1)
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col =  j + dir[1];
            if (isValid(row, col) && !visited[row][col] && dist[row][col] >= minDist) {
                if (dfs(row, col, minDist, visited))
                    return true;
            }
        }
        return false;
    }

    private boolean isValid(int i, int j) {
        return i >=0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dist, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
}

int[][] visited数组，visited数组只需要创建一次

要初始化为-1，因为会考虑到limit == 0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        dist = new int[n][n];
        visited = new int[n][n];
        for (int[] arr : visited)
            Arrays.fill(arr, -1);
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = g.get(i).get(j);
                dist[i][j] = -1;
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    dist[i][j] = 0;
                }
            }
        }
        // 多源BFS
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int i = node[0], j = node[1];
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col) && dist[row][col] == -1) {
                    dist[row][col] = dist[i][j] + 1;
                    queue.offer(new int[]{row, col});
                }
            }
        }
        int l = 0, r = 2 * (n - 1);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }

    private boolean check(int limit) {
        if (dist[0][0] < limit)
            return false;
        return dfs(0, 0, limit);
    }

    private boolean dfs(int i, int j, int limit) {
        if (i == n - 1 && j == n - 1)
            return true;
        visited[i][j] = limit;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row,col) && visited[row][col] != limit && dist[row][col] >= limit && dfs(row, col, limit)) {
                return true;
            }
        }
        return false;
    }

    int[][] grid, dist, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;
    int[][] visited;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }
}

方法二：多源BFS + 并查集

关于从dists.size() - 2开始枚举：最后一步是空集，所以最大的距离为 dists.size() - 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
    public int maximumSafenessFactor(List<List<Integer>> g) {
        n = g.size();
        grid = new int[n][n];
        int[][] dist = new int[n][n];
        for (int[] arr : dist)
            Arrays.fill(arr, -1);
        List<int[]> queue = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = g.get(i).get(j);
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }
        // 多源BFS
        List<List<int[]>> dists = new ArrayList<>();
        dists.add(queue);
        List<int[]> temp = new LinkedList<>();
        while (!queue.isEmpty()) {
            temp = queue;
            queue = new LinkedList<>();
            for (int[] node : temp) {
                for (int[] dir : dirs) {
                    int row = node[0] + dir[0], col = node[1] + dir[1];
                    if (isValid(row, col) && dist[row][col] == -1) {  // 没有被访问过
                        queue.add(new int[]{row, col});
                        dist[row][col] = dists.size();
                    }
                }
            }
            // 最后一步是空集，所以最大的距离为 dists.size() - 2
            dists.add(queue);
        }
        // 初始化并查集
        init(n * n);
        for (int i = dists.size() - 2; i > 0; --i) {
            List<int[]> q = dists.get(i);
            for (int[] node : q) {
                for (int[] dir : dirs) {
                    int row = node[0] + dir[0], col = node[1] + dir[1];
                    if (isValid(row, col) && dist[row][col] >= i)
                        union(node[0] * n + node[1],row * n + col);
                }
            }
            if (findParent(0) == findParent(n * n - 1))
                return i;
        }
        return 0;
    }



    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < n && j < n;
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n;

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

补充题 1631. 最小体力消耗路径

方法一：多源BFS + 二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int minimumEffortPath(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        visited = new boolean[m][n];
        int l = 0, r = (int) 1e6;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int limit) {
        visited = new boolean[m][n];
        return dfs(0, 0, limit);
    }

    private boolean dfs(int i, int j, int limit) {
        if (i == m - 1 && j == n - 1)
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && !visited[row][col] && Math.abs(heights[i][j] - heights[row][col]) <= limit)
                if (dfs(row, col, limit))
                    return true;
        }
        return false;
    }


    int[][] heights, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    boolean[][] visited;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

方法二：并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public int minimumEffortPath(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        visited = new boolean[m][n];
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int id = i * n + j;
                if (i > 0)
                    edges.add(new int[]{id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])});
                if (j > 0)
                    edges.add(new int[]{id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])});
            }
        }
        Collections.sort(edges, (o1, o2) -> o1[2] - o2[2]);
        // 初始化并查集
        init(m * n);
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            union(from, to);
            if (findParent(0) == findParent(m * n - 1))
                return weight;
        }
        return 0;
    }

    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }



    int[][] heights, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    boolean[][] visited;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

在网格图中访问一个格子的最少时间

二刷 dijkstra

无需visited数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[1][0] > 1 && grid[0][1] > 1)
            return -1;
        int[][] dist = new int[m][n];
        for (int[] arr : dist)
            Arrays.fill(arr, Integer.MAX_VALUE >> 1);
        dist[0][0] = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
        q.offer(new int[]{0, 0, 0});
        while (true) {
            int[] node = q.poll();
            int i = node[0], j = node[1], d = node[2];
            if (i == m - 1 && j == n - 1)
                return d;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col, m, n)) {
                    int nd = Math.max(d, grid[row][col]);
                    nd += (nd + row + col) % 2;
                    if (nd < dist[row][col]) {
                        dist[row][col] = nd;
                        q.offer(new int[]{row, col, nd});
                    }
                }
            } 
        }
    }

    
    public boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int[][] dirs = new int[][]{{1,0}, {-1,0}, {0, 1}, {0, -1}};
    
}

方法一：堆优化的dijkstra

dist[i][j]与 i + j 同奇偶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int minimumTime(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1)
            return -1;
        int[][] dist = new int[m][n];
        int inf = Integer.MAX_VALUE >> 1;
        for (int[] arr : dist)
            Arrays.fill(arr, inf);
        dist[0][0] = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o1[0] - o2[0]));
        queue.offer(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int d = arr[0], i = arr[1], j = arr[2];
            if (i == m - 1 && j == n - 1)
                return d;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col)) {
                    int nd = Math.max(d + 1, grid[row][col]);
                    nd += (nd - row - col) % 2;
                    if (nd < dist[row][col]) {
                        dist[row][col] = nd;
                        queue.offer(new int[]{nd, row, col});
                    }
                }
            }
        }
        return dist[m - 1][n - 1];
    }

    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

方法二：二分+ BFS

双数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int minimumTime(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1)
            return -1;
        int left = Math.max(m + n - 2, grid[m - 1][n - 1]), right = (int) 1e5 + m + n;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (check(mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left + (left + m + n) % 2; // 答案要与 m + n - 2同奇偶
    }

    private boolean check(int limit) {
        boolean[][] visited = new boolean[m][n];
        visited[m - 1][n - 1] = true;
        List<int[]> queue = new ArrayList<>();
        int t = limit - 1;
        queue.add(new int[]{m - 1, n - 1});
        while (!queue.isEmpty()) {
            List<int[]> temp = queue;
            queue = new ArrayList<>();
            for (int[] arr : temp) {
                int i = arr[0], j = arr[1];
                for (int[] dir : dirs) {
                    int row = i + dir[0], col = j + dir[1];
                    if (isValid(row, col) && !visited[row][col] && grid[row][col] <= t) {
                        if (row == 0 && col == 0)
                            return true;
                        visited[row][col] = true;
                        queue.add(new int[]{row, col});
                    }
                }
            }
            --t;
        }
        return false;
    }



    int[][] grid, dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
}

Queue

q.offer(new int[]{m - 1, n - 1, limit - 1});表示终点在limit时访问过，邻居的grid值要小于limit - 1

从limit - 1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[1][0] > 1 && grid[0][1] > 1)
            return -1;
        int l = Math.max(m + n - 2, grid[m - 1][n - 1]), r = (int) 1e5;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, grid, m, n))
                r = mid - 1;
            else 
                l = mid + 1;
        }
        return l + (l + m + n - 2) % 2; // 答案需要和重点坐标[m - 1, n - 1]之和同奇偶
    }

    public boolean check(int limit, int[][] grid, int m, int n) {
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{m - 1, n - 1, limit - 1});
        visited[m - 1][n - 1] = true;
        while (!q.isEmpty()) {
            int[] node = q.poll();
            int i = node[0], j = node[1], t = node[2];
            if (i == 0 && j == 0)
                return true;
            for (int[] dir : dirs) {
                int row = i + dir[0], col = j + dir[1];
                if (isValid(row, col, m, n) && !visited[row][col] && t >= grid[row][col]) {
                    q.offer(new int[]{row, col, t - 1});
                    visited[row][col] = true;
                }
            }
        }
        return false;
    }
    
    public boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int[][] dirs = new int[][]{{1,0}, {-1,0}, {0, 1}, {0, -1}};
    
}

单源最短路

743. 网络延迟时间

方法一：Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] graph = new int[n + 1][n + 1];
        for (int[] arr : graph)
            Arrays.fill(arr, inf);
        for (int[] t : times) {
            int from = t[0], to = t[1], cost = t[2];
            graph[from][to] = cost;
        }
        int[] dist = dijkstra(graph, times, n, k);
        int res = -1;
        for (int i = 1; i < dist.length; ++i) {
            if (dist[i] == inf)
                return -1;
            res = Math.max(res, dist[i]);
        }
        return res;
    }  

    public int[] dijkstra(int[][] graph, int[][] times, int n, int from) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, inf);
        dist[from] = 0;
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        queue.offer(new int[]{from, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int node = arr[0], d = arr[1];
            if (visited[node])
                continue;
            visited[node] = true;
            for (int i = 1; i <= n; ++i) {
                if (!visited[i] && dist[i] > d + graph[node][i]) {
                    dist[i] = d + graph[node][i];
                    queue.offer(new int[]{i, dist[i]});
                }
            }
        }
        return dist;
    }
        int inf = Integer.MAX_VALUE >> 1;
    
}

方法一：Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        List<Map<Integer, Double>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new HashMap<>());
        }
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            double prob = succProb[i];
            graph.get(from).put(to, prob);
            graph.get(to).put(from, prob);
        }
        return dijkstra(n, start_node, end_node, graph);
    }

    public double dijkstra(int n, int from, int to, List<Map<Integer, Double>> graph) {
        boolean[] visited = new boolean[n];
        double[] dist = new double[n];
        Arrays.fill(dist, 0.0);
        dist[from] = 1.0;
        PriorityQueue<double[]> queue = new PriorityQueue<>((o1, o2) -> Double.compare(o2[1], o1[1]));
        queue.offer(new double[]{(double) from, 1.0});
        while (!queue.isEmpty()) {
            double[] node = queue.poll();
            int currNode = (int) node[0];
            double d = node[1]; 
            if (visited[currNode])
                continue;
            visited[currNode] = true;
            if (currNode == to) {
                return d;
            }
            for (Map.Entry<Integer, Double> entry : graph.get(currNode).entrySet()) {
                int nextNode = entry.getKey();
                double prob = entry.getValue();
                if (!visited[nextNode] && dist[nextNode] < d * prob) {
                    dist[nextNode] = d * prob;
                    queue.offer(new double[]{(double) nextNode, dist[nextNode]});
                }
            }
        }
        return 0.0;
    }



}

1631. 最小体力消耗路径

方法一：二分 + DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int minimumEffortPath(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        int l = 0, r = (int) 1e6;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    public boolean check(int limit) {
        visited = new boolean[m][n];
        return dfs(0, 0, limit);
    }

    

    public boolean dfs(int i, int j, int limit) {
        if (i == m - 1 && j == n - 1)
            return true;
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (isValid(row, col) && !visited[row][col] && Math.abs(heights[i][j] - heights[row][col]) <= limit && dfs(row, col, limit)) {                return true;
            }
        }
        return false;
    }

    public boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }
 
    int[][] heights, dirs = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    int m, n;
    boolean[][] visited;
    
}

1368. 使网格图至少有一条有效路径的最小代价

方法一：Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int minCost(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] arr : dist)
            Arrays.fill(arr, inf);
        dist[0][0] = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));
        queue.offer(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int x = arr[0], y = arr[1], d = arr[2];
            if (visited[x][y])
                continue;
            visited[x][y] = true;
            for (int i = 1; i <= 4; ++i) {
                int[] dir = dirs[i];
                int row = x + dir[0], col = y + dir[1], cost = (i == grid[x][y] ? 0 : 1);
                if (isValid(row, col) && !visited[row][col] && dist[row][col] > d + cost) {
                    dist[row][col] = d + cost;
                    queue.offer(new int[]{row, col, dist[row][col]});
                }
            }
        }
        return dist[m - 1][n - 1];
    }


    public boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < m && j < n;
    }

    int m, n, inf = Integer.MAX_VALUE;
    int[][] grid, dirs = new int[][]{{0, 0}, {0, 1}, {0, -1},  {1, 0}, {-1, 0}};
    
}

全源最短路

Algorithms > Graph
#图 #最短路
Shortest Path Problem
https://leopol1d.github.io/2023/05/31/shortest-path-problem/
作者
Leopold
发布于
2023年5月31日
许可协议