Dijkstra迪杰斯特拉算法Java模板

package lanqiao;

import java.util.Arrays;

public class Dijkstra {
    public static void main(String[] args) {
        int n = 2021;
        int[][] map = new int[n + 1][n + 1]; // 二维矩阵存储各个点以及关系
        // 还有一种邻接表 使用动态的方式来存储 这样可以节省空间

        // 构造无向图 这里可以换成你需要的构建图方式
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n && j < i + 22; j++) {
                // 有向图的构造需要 动态添加比较好 或者仅更新一个节点 为0的节点就是不连通点，查找某一个点的其他连接点时需要判断 != 0
                map[i][j] = map[j][i] = lcm(i, j);
            }
        }

        // dijkstra算法 1-2021
        int[] dist = new int[n + 1]; // 由特殊路径得到的最短路径
        Arrays.fill(dist, Integer.MAX_VALUE); // 填充最大值 方便更新
        int[] pre = new int[n + 1]; // 前驱节点
        int[] s = new int[n + 1]; // 确定的点
        s[1] = 1;
        pre[1] = 0;
        dist[1] = 0;
        int cnt = 1;

        // 寻找当前点可以到达的下一个所有点 取其中最小的长度作为下一个确定最短路径的点
        // 从刚刚确定的那个点出发 寻找下一个到达的所有点 重复此过程 直到找到目标点
        int idx = 1; // idx就是当前点
        while (cnt != n) {
            int i = idx;
                // 开始找当前点下一个所有点 并更新 dist 以及 pre
                for (int j = 1; j <= n; j++) {
                    // map[i][j] s[j] == 0 是找没有确定最短路径的点 map[i][j] != 0 是找连通的点 
                    if (s[j] == 0 && map[i][j] != 0 && map[i][j] + dist[i] < dist[j]) {
                        dist[j] = map[i][j] + dist[i];
                        pre[j] = i;
                    }
                }
                // 查找完毕 更新完毕 找当前dist中未确定最短距离即s中为0 并且 最短的距离的点，这个点就是下一个确认的最短距离的点
                int minDist = Integer.MAX_VALUE;
                for (int k = 1; k <= n; k++) {
                    if (s[k] == 0) {
                        if (dist[k] < minDist) {
                            minDist = Math.min(idx, dist[k]);
                            idx = k;
                        }
                    }
                }
                // idx就是下一个进入s的节点
                s[idx] = 1;
                cnt++;
        }

        System.out.println(dist[n]);

    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}

迪杰斯特拉算法总结：

1. 构造图，可以使用二维矩阵，邻接表(Vector,ArrayList)。
   如果不是连续的节点，可以把这些节点当作连续的，然后再构造的图中存储相应的Node节点或数据即可。
2. 使用三个数组。
   **s[]**用来存放所有节点的下标，0表示未确定，1表示已经确定。
   **dist[]**用来存放原点到某一个节点的路径长度，首先存放特殊路径，即从当前点到其下一个节点的距离，然后进行更新，得到最短距离。
   **pre[]**用来存放当前下标对应节点的前驱节点的下标。有了它就可以输出整条路径了。