最短路径的两个算法

Dijkstra — 单源最短路基于dfs

Floyd算法 — 多源最短路基于矩阵

SPFA算法 — 单源最短路

本文主要介绍 Dijkstra 在Java中的使用

(Dijkstra)迪杰斯特拉算法解决的问题是：

在一个有向图中，求图中一个节点到其他所有节点的最短距离

算法思路：

每次选取一个离出发点最近且未标记的节点，调整出发点到以这个节点为中心的周边节点的最短距离。这个过程持续 n - 1 次，直到所有节点都遍历完毕。

假设有一个这样的图（图片出处：Dijkstra算法Java实现）：

1.求节点 1 到其他节点的最短距离

思路：

记录 start 点到各点的最短路径长度
找出一个未标记的离出发点最近的节点(最短边)
标记该节点为已经访问过
基于该点更新其他点到start点的距离

循环往复到遍历完所有节点

public class Test {
    public static void main(String[] args) {
        int MAX = Integer.MAX_VALUE;    // 无法到达时距离设为 Integer.MAX_VALUE
        int[][] weight={
                {0,1,12,MAX,MAX,MAX},
                {MAX,0,9,3,MAX,MAX},
                {MAX,MAX,0,MAX,5,MAX},
                {MAX,MAX,4,0,13,15},
                {MAX,MAX,MAX,MAX,0,4},
                {MAX,MAX,MAX,MAX,MAX,0}
        };
        int start = 0;  // 选择出发点
        System.out.println(Arrays.toString(solution(weight,start)));
    }

    private static int[] solution(int[][] weight, int start) {
        boolean[] visit = new boolean[weight.length]; // 标记某节点是否被访问过
        int[] res = new int[weight.length];     // 记录 start 点到各点的最短路径长度
        for (int i = 0; i < res.length; i++) {
            res[i] = weight[start][i];
        }

        // 查找 n - 1 次（n 为节点个数），每次确定一个节点
        for(int i = 1; i < weight.length; i++) {
            int min = Integer.MAX_VALUE;
            int p = 0;
            // 找出一个未标记的离出发点最近的节点
            for(int j = 0; j < weight.length; j++){
                if(j != start && !visit[j] && res[j] < min){
                    min = res[j];
                    p = j;
                }
            }
            // 标记该节点为已经访问过
            visit[p] = true;

            for (int j = 0; j < weight.length; j++){
                if (j == p || weight[p][j] == Integer.MAX_VALUE) {  // p 点不能到达 j
                    continue;
                }
                if (res[p] + weight[p][j] < res[j]){
                    res[j] = res[p] + weight[p][j];  //更新最短路径
                }
            }
        }

        return res;
    }
}

2.求从矩阵左上角到右下角的最短距离

leetcode 778. 水位上升的泳池中游泳

public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] directions = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        boolean[][] visited = new boolean[n][n];
        //优先队列，最小的先出来
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[2]-o2[2];
            }
        });
        queue.offer(new int[]{0,0,grid[0][0]});
        int ans = 0;
        while(!queue.isEmpty()){
            int[] temp = queue.poll();
            int x = temp[0];
            int y = temp[1];
            int dp = temp[2];
            ans = Math.max(ans,dp);
            if(x==n-1 && y==n-1){
                return ans;
            }
            //弹出来之后再标记，确定此刻为最小
            visited[x][y] = true;
            for(int[] dir:directions){
                int nx = x+dir[0];
                int ny = y+dir[1];
                if(nx>=0 && nx<n && ny>=0 &&ny<n && !visited[nx][ny]){
                    queue.offer(new int[]{nx,ny,grid[nx][ny]});
                }
            }
        }
        return ans;
    }

使用BFS遍历所有路径，但是使用优先队列替换普通队列，实现最短路径查询

参考

Dijkstra算法Java实现