38.迪杰斯特拉（Dijkstra）算法

概述

我们在上一篇中面对修路的问题讲述了普利姆算法的实现方式，本篇我们参照迪杰斯特拉算法来对修路问题做进一步拆解。
我们回顾一下之前的问题：

“要想富，先修路”，郝乡长最近为了德胜乡修路的事情愁白了头。
得胜乡有A、B、C、D、E、F、G七个村子，现在需要修路把7个村庄连通，但是又想要耗费的公路建材最少（修建公路的总里程最短），聪明的你是否有什么好办法呢？
注：各个村庄的距离用边线（权值）来表示。

算法说明

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

算法过程

设置出发顶点为v，顶点集合V{v1,v2,v3…}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,d3…}，Dis集合记录着v到图中各顶点的距离(到自身可以看作0，v到vi距离对应为di)

1. 从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时的v到vi即为最短路径
2. 更新Dis集合，更新规则为: 比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi到达的)
3. 重复执行两步骤，直到最短路径顶点为目标顶点即可结束

数组说明

• already_arr 表示访问过的顶点，0-未访问；1-已访问；
• dis 表示出发顶点到对应顶点的距离；
• pre_visited 表示各个节点的前驱节点；

过程说明

1. 初始化认为到每个顶点的距离都是最大；
2. 到自己的距离为0；
3. 前驱顶点访问前初始化均为0；
   以G为出发顶点访问过一次后
4. dis对应更新为 [ 2 , 3 , 65535 , 65535 , 4 , 6 ，0 ] , 即把G到所有顶点的距离都算了一遍，（把比原值小的部分）更新到dis数组，可以参考邻接矩阵G行;
5. pre_visited 对应更新为 [ 6 , 6 , 0 , 0 , 6 , 6 , 0 ] , 表示下标6的顶点G是A,B,E,F的前驱节点，自己（G）的前驱节点可不考虑；
   此时，G出发已经访问了A,B,E,F ,遵循广度优先原则， 按顺序下面需要把A作为新的访问顶点 开始进行广度遍历访问（注意并不等同于出发顶点，这也是为什么要记录）

代码实现

public class DijkstraAlgorithm {

    public static void main(String[] args) {
        char[] vertex = {'A','B','C','D','E','F','G'};
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;//表示不可连接
        matrix[0] = new int[]{N,5,7,N,N,N,2};
        matrix[1] = new int[]{5,N,N,9,N,N,3};
        matrix[2] = new int[]{7,N,N,N,8,N,N};
        matrix[3] = new int[]{N,9,N,N,N,4,N};
        matrix[4] = new int[]{N,N,8,N,N,5,4};
        matrix[5] = new int[]{N,N,N,4,5,N,6};
        matrix[6] = new int[]{2,3,N,N,4,6,N};
        //创建Graph对象
        Graph graph = new Graph(vertex,matrix);
        //测试，看看是否Ok
        graph.showGraph();

        //测试迪杰斯特拉算法
        graph.dsj(6);//假设从G出发，G下标是6

        //输出结果
        graph.showDijkstra();
    }

}

//已访问顶点集合
class VisitedVertex{
    //记录各个顶点是否访问过 1-访问过，0-未访问；  动态更新
    public int [] already_arr;
    //每个下标对应的值为前一个顶点下标，会动态更新
    public int [] pre_visited;
    //记录出发顶点到其它所有顶点的距离，比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求得最短就离会存放到dis
    public int [] dis;

    /**
     * @param length 表示顶点个数
     * @param index 出发顶点对应的下标，比如G顶点，下标就是6
     */
    public VisitedVertex(int length,int index){
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        //初始化dis
        this.already_arr[index] = 1;//设置出发顶点被访问  置为1
        Arrays.fill(dis,65535);
        this.dis[index]=0;//设置出发顶点 的访问距离为0
    }

    /**
     * 功能： 判断index顶点是否被访问过
     * @param index
     * @return 如果访问过，就返回true,否则返回false
     */
    public boolean in(int index){
        return already_arr[index]==1;
    }

    /**
     * 更新出发顶点到index顶点的距离
     * @param index
     * @param len
     */
    public void updateDis(int index,int len){
        dis[index] = len;
    }

    /**
     * 功能：更新pre顶点的前驱为index节点
     * @param pre
     * @param index
     */
    public void updatePre(int pre,int index){
        pre_visited[pre] = index;
    }

    /**
     * 返回出发顶点到index的距离
     * @param index
     */
    public int getDis(int index){
        return dis[index];
    }

    //继续选择并返回新的访问顶点，比如这里的G 完后， 就是A作为新的访问顶点（注意不是出发顶点）
    public int updateArr(){
        int min = 65535,index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i]==0&&dis[i]<min){
                min = dis[i];
                index = i;
            }
        }
        //更新index顶点被访问过
        already_arr[index] = 1;
        return index;
    }

    //显示最后的结果
    //将三个数组输出
    public void show(){
        System.out.println("==============================");
        //输出already_arr
        for (int i : already_arr) {
            System.out.print(i+" ");
        }
        System.out.println();
        //输出pre_visited
        for (int i : pre_visited) {
            System.out.print(i+" ");
        }
        System.out.println();
        //输出dis
        for (int i : dis) {
            System.out.print(i+" ");
        }
        System.out.println();

        //为了最短距离看起来美观，处理
        char[] vetex = {'A','B','C','D','E','F','G'};
        int count = 0 ;
        for (int i : dis) {
            if (i!=65535){
                System.out.print(vetex[count]+"("+i+")");
            }else {
                System.out.print("N");
            }
            count++;
        }
        System.out.println();
    }

}

//图
class Graph{
    private char[] vertex;//顶点数组
    private int [][] matrix;//邻接矩阵
    private VisitedVertex vv;//已经访问的顶点集合

    //构造器
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    //显示结果
    public void showDijkstra(){
        vv.show();
    }

    //显示图
    public void showGraph(){
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    //迪杰斯特拉（Dijkstra）算法实现
    /**
     * @param index 出发顶点对应的下标
     */
    public void dsj(int index){
        vv = new VisitedVertex(vertex.length, index);
        update(index);//更新Index下标顶点到周围顶点的距离和前驱节点

        for (int j = 0; j < vertex.length; j++) {
            index =vv.updateArr();//选择并返回新的访问顶点
            update(index); //更新Index下标顶点到周围顶点的距离和前驱节点
        }
    }

    //更新index下标到周围顶点的距离和周围顶点的前驱顶点
    private void update(int index){
        int len = 0;
        //根据遍历邻接矩阵的matrix[index]行
        for (int j = 0; j < matrix[index].length; j++) {
            //len 含义是： 出发顶点到Index顶点的距离 + index顶点到j顶点的距离之和
            len = vv.getDis(index)+matrix[index][j];
            //如果j没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
            if (!vv.in(j)&&len<vv.getDis(j)){
                vv.updatePre(j,index);//更新j顶点的前驱为Index顶点
                vv.updateDis(j,len);//更新出发顶点到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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

---

关注我，共同进步，每周至少一更。——Wayne