操作步骤

(1) 初始时，S只包含起点vs；U包含除vs外的其他顶点，且U中顶点的距离为"起点vs到该顶点的距离"[例如，U中顶点v的距离为(vs,v)的长度，然后vs和v不相邻，则v的距离为∞]。
(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
(3) 更新U中各个顶点到起点vs的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(vs,v)的距离可能大于(vs,k)+(k,v)的距离。
(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

代码实现

package dataStructure.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * Dijkstra最短路径
 */
public class ShortestPathDijkstra {
    private int[][] matrix;//邻接矩阵
    private int N = Integer.MAX_VALUE;//表示正无穷
    private String[] vertexes;//表示顶点集合

    private void createGraph(int index) {
        matrix = new int[index][index];
        vertexes = new String[index];

        int[] v0 = {0, 1, 5, N, N, N, N, N, N};
        int[] v1 = {1, 0, 3, 7, 5, N, N, N, N};
        int[] v2 = {5, 3, 0, N, 1, 7, N, N, N};
        int[] v3 = {N, 7, N, 0, 2, N, 3, N, N};
        int[] v4 = {N, 5, 1, 2, 0, 3, 6, 9, N};
        int[] v5 = {N, N, 7, N, 3, 0, N, 5, N};
        int[] v6 = {N, N, N, 3, 6, N, 0, 2, 7};
        int[] v7 = {N, N, N, N, 9, 5, 2, 0, 4};
        int[] v8 = {N, N, N, N, N, N, 7, 4, 0};

        matrix[0] = v0;
        matrix[1] = v1;
        matrix[2] = v2;
        matrix[3] = v3;
        matrix[4] = v4;
        matrix[5] = v5;
        matrix[6] = v6;
        matrix[7] = v7;
        matrix[8] = v8;

        vertexes[0] = "v0";
        vertexes[1] = "v1";
        vertexes[2] = "v2";
        vertexes[3] = "v3";
        vertexes[4] = "v4";
        vertexes[5] = "v5";
        vertexes[6] = "v6";
        vertexes[7] = "v7";
        vertexes[8] = "v8";
    }

    /**
     * Dijkstra最短路径
     */
    public void dijkstra(int vs){
        //表示最短路径是否获取成功
        boolean[] flag = new boolean[vertexes.length];
        //还未求出的最短路径
        int[] U = new int[vertexes.length];
        //前驱顶点数组:用于打印
        int[] pre = new int[vertexes.length];
        //已求出的最短路径的节点
        String[] S = new String[vertexes.length];

        //初始化
        for (int i = 0; i < vertexes.length; i ++) {
            flag[i] = false;
            U[i] = matrix[vs][i];
            pre[i] = 0;
        }

        //将vs移除
        S[0] = vertexes[vs];
        flag[vs] = true;
        U[vs] = 0;

        int k = 0;
        for(int i = 1; i < vertexes.length; i++){
            //获取最短路径的节点:该点到vs的值最小
            int min = N;
            for(int j = 0; j < vertexes.length; j ++){
                if(flag[j] == false && U[j] < min){
                    min = U[j];
                    k = j;
                }
            }

            //将k放在s中
            S[i] = vertexes[k];
            flag[k] = true;

            //更新未访问的节点:v[1]的集体加个最短路径
            for (int j = 0; j < vertexes.length; j++) {
                int tmp = (matrix[k][j] == N) ? N : (min + matrix[k][j]);
                //未访问过且值不为0的更新
                if(flag[j] == false && (tmp < U[j])){//若tmp小于U[j],只用一种可能是U[j]=0
                    U[j] = tmp;
                    pre[j] = k;//下标节点
                }
            }
        }

        //打印最短路径
        System.out.println("起始顶点: " + vertexes[vs]);
        for(int i = 0; i < vertexes.length; i++){
            System.out.println("最短路径(" + vertexes[vs] + "," + vertexes[i] +"):" + U[i] + "   ");

            //输出v0->v1->v2->v4
            List<String> path = new ArrayList<>();
            int j = i;
            while(true){
                path.add(vertexes[j]);

                if(j == 0){
                    break;
                }

                j = pre[j];
            }
            for(int x = path.size() -1; x >= 0; x--){
                if(x == 0){
                    System.out.println(path.get(x));
                }else{
                    System.out.print(path.get(x) + "->");
                }
            }
        }

        System.out.println("顶点放入s的顺序:");
        //v0-->v1-->v2-->v4-->v3-->v5-->v6-->v7-->v8
        for(int i = 0; i < vertexes.length; i++){
            System.out.print(S[i]);

            if(i != vertexes.length - 1){
                System.out.print("-->");
            }
        }

    }

    public static void main(String[] args) {
        ShortestPathDijkstra shortestPathDijkstra = new ShortestPathDijkstra();
        shortestPathDijkstra.createGraph(9);
        shortestPathDijkstra.dijkstra(0);
        /**
         起始顶点: v0
         最短路径(v0,v0):0   
         v0
         最短路径(v0,v1):1   
         v0->v1
         最短路径(v0,v2):4   
         v0->v1->v2
         最短路径(v0,v3):7   
         v0->v1->v2->v4->v3
         最短路径(v0,v4):5   
         v0->v1->v2->v4
         最短路径(v0,v5):8   
         v0->v1->v2->v4->v5
         最短路径(v0,v6):10   
         v0->v1->v2->v4->v3->v6
         最短路径(v0,v7):12   
         v0->v1->v2->v4->v3->v6->v7
         最短路径(v0,v8):16   
         v0->v1->v2->v4->v3->v6->v7->v8
         顶点放入s的顺序:
         v0-->v1-->v2-->v4-->v3-->v5-->v6-->v7-->v8
         */
    }

}