Dijkstra算法

方式一

    public static void main(String[] args) {
        String[] vertexs = {"A", "B", "C", "D", "E", "F"};
       
        HashMap<String, HashMap<String, Integer>> graph = new HashMap<>();
        HashMap<String, Integer> temp1 = new HashMap<>();
        HashMap<String, Integer> temp2 = new HashMap<>();
        HashMap<String, Integer> temp3 = new HashMap<>();
        HashMap<String, Integer> temp4 = new HashMap<>();
        HashMap<String, Integer> temp5 = new HashMap<>();
        HashMap<String, Integer> temp6 = new HashMap<>();
        temp1.put("A", 0);
        temp1.put("B", 2);
        temp1.put("C", 4);
        graph.put("A", temp1);

        temp2.put("A", 2);
        temp2.put("B", 0);
        temp2.put("C", 1);
        temp2.put("E", 4);
        graph.put("B", temp2);

        temp3.put("A", 1);
        temp3.put("B", 1);
        temp3.put("C", 0);
        temp3.put("D", 2);
        temp3.put("E", 3);
        graph.put("C", temp3);

        temp4.put("C", 2);
        temp4.put("D", 0);
        temp4.put("E", 3);
        graph.put("D", temp4);

        temp5.put("B", 4);
        temp5.put("C", 3);
        temp5.put("D", 3);
        temp5.put("E", 0);
        temp5.put("F", 1);
        graph.put("E", temp5);


        temp6.put("E", 1);
        temp6.put("F", 0);
        graph.put("F", temp6);

        Dijkstra(graph, "A", vertexs);

    }


    public static void Dijkstra(HashMap<String, HashMap<String, Integer>> graph, String vertex, String[] vertexs) {
        //已访问节点
        HashSet<String> visited = new HashSet<>();
        //记录节点的父节点
        HashMap<String, String> parent = new HashMap<>();
        //初始节点父节点为空
        parent.put(vertex, null);

        //初始化初始节点到各节点的距离
        HashMap<String, Integer> dist = initDistance(graph, vertex);
        System.out.println(dist.toString());
        
        while (visited.size() != vertexs.length) {
            int minLen = Integer.MAX_VALUE;
            String minKey = null;
            //获取最短路径的节点
            for (String key : graph.get(vertex).keySet()) {
                if (!visited.contains(key)){
                    Integer pathLen = graph.get(vertex).get(key);
                    if (pathLen < minLen) {
                        minLen = pathLen;
                        minKey = key;
                    }
                }
            }
            //将给节点加入到以访问集合
            visited.add(minKey);

            //根据该最短路径节点更新初始节点到所有未访问节点的距离
            for (String key : graph.get(minKey).keySet()) {
                if (!visited.contains(key)) {
                    int expect = minLen + graph.get(minKey).get(key);
                    if (dist.get(key) >= expect) {
                        dist.put(key, expect);
                        parent.put(key, minKey);
                        graph.get(vertex).put(key, expect);
                    }
                }
            }
        }
        System.out.println(parent.toString());
        System.out.println(dist.toString());

    }

    public static HashMap<String, Integer> initDistance(HashMap<String, HashMap<String, Integer>> graph, String vertex) {
        int init = Integer.MAX_VALUE;
        HashMap<String, Integer> dist = new HashMap<>();
        for (String key : graph.keySet()) {
            if (graph.get(vertex).get(key)!=null) {
                dist.put(key, graph.get(vertex).get(key));
            }else{
                dist.put(key, init);
            }
        }
        return dist;
    }

方式二

import java.util.Arrays;

/**
 * @Author Noperx
 * @Create 2021-07-05 22:53
 */
public class Dijkstra {

    public static void main(String[] args) {
        String[] vertexs = {"A", "B", "C", "D", "E", "F"};
        //邻接矩阵
        int[][] matrix = new int[vertexs.length][vertexs.length];
        final int N = 65535;// 表示不可以连接
        matrix[0] = new int[]{0, 5, 4, N, N, N};
        matrix[1] = new int[]{5, 0, 1, N, 4, N};
        matrix[2] = new int[]{4, 1, 0, 2, 3, N};
        matrix[3] = new int[]{N, N, 2, 0, 3, N};
        matrix[4] = new int[]{N, 4, 3, 3, 0, 1};
        matrix[5] = new int[]{N, N, N, N, 1, 0};

        dijkstra(matrix, vertexs, "F");

    }

    public static void dijkstra(int[][] matrax, String[] vertexs, String vertex){
        int n = vertexs.length;
        //记录已访问节点的下标
        int[] visited = new int[n];
        //记录每个节点父节点的下标
        int[] parent = new int[n];

        int initIndex = -1;
        //获取初始节点的下标
        for (int i = 0; i < n; i++) {
            if (vertexs[i].equals(vertex)){
                initIndex = i;
            }
        }
        //初始节点的父节点不存在
        parent[initIndex] = initIndex;

        int minEdge = Integer.MAX_VALUE;
        int minIndex = initIndex;
        int count = 1;
        while (count!=n){
            for (int i = 0; i < matrax[initIndex].length; i++) {
                if (visited[i]!=1 && matrax[initIndex][i]<minEdge){
                    minEdge = matrax[initIndex][i];
                    minIndex = i;
                }
            }
            visited[minIndex] = 1;
            count++;
            minEdge = Integer.MAX_VALUE;

            for (int i = 0; i < matrax[initIndex].length; i++) {
                if (visited[i]!=1 && matrax[initIndex][i] >= matrax[initIndex][minIndex]+matrax[minIndex][i]){
                    matrax[initIndex][i] = matrax[initIndex][minIndex]+matrax[minIndex][i];
                    parent[i] = minIndex;
                }else{
                }
            }
            System.out.println("加入节点"+vertexs[minIndex]);
            System.out.println(Arrays.toString(matrax[initIndex]));
        }
        System.out.println("父节点下标");
        System.out.println(Arrays.toString(parent));
        for (int i = 0; i < parent.length; i++) {
            System.out.println(vertexs[i]+"->"+vertexs[parent[i]]);
        }
    }
}

输出

加入节点F
[65535, 65535, 65535, 65535, 1, 0]
加入节点E
[65535, 5, 4, 4, 1, 0]
加入节点C
[8, 5, 4, 4, 1, 0]
加入节点D
[8, 5, 4, 4, 1, 0]
加入节点B
[8, 5, 4, 4, 1, 0]
父节点下标
[2, 4, 4, 4, 0, 5]
A->C
B->E
C->E
D->E
E->A
F->F