算法7：迪杰斯特拉算法

1. 应用场景-最短路径问题

• 看一个应用场景和问题

1. 胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
2. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里
3. 问：如何计算出G村庄到其它各个村庄的最短距离?
4. 如果从其它点出发到各个点的最短距离又是多少?

2. 迪杰斯特拉(Dijkstra)算法介绍

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

3. 迪杰斯特拉(Dijkstra)算法过程

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

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

4. 算法分析过程

• 先定义三个数组，分别是已访问节点、前驱节点、出发顶点到其他顶点的距离

//已访问顶点集合
class Visited_vertex{
	//记录各个顶点是否访问过  1表示访问过,0未访问,会动态更新
	public int[] already_arr; 
	//每个下标对应的值为前一个顶点下标, 会动态更新
	public int[] pre_visited;
	//记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
	public int[] dis;
}
1
2
3
4
5
6
7
8
9

• 假设邻接矩阵如下，N（65535）表示不连通

  A B C D E F G
A{N,5,7,N,N,N,2};  
B{5,N,N,9,N,N,3};  
C{7,N,N,N,8,N,N};  
D{N,9,N,N,N,4,N};  
E{N,N,8,N,N,5,4};  
F{N,N,N,4,5,N,6};  
G{2,3,N,N,4,6,N};  
1
2
3
4
5
6
7
8

• 以G点为出发顶点，初始化后

• 以G为出发顶点访问过一次后的情况

• 经过G出发访问一轮后，继续选择并返回新的访问顶点， 比如访问G之后，就是以 A点作为新的访问顶点(注意不是出发顶点)，遍历所有的顶点，即可得到

5. 代码实现

import java.util.Arrays;

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);
        // 显示图
        graph.showGraph();
        // 以G作为出发顶点
        graph.dsj(6);
        graph.showDijkstra();
    }
}

// 已访问顶点的集合
class VisitedVertex {
    // 记录各个顶点是否访问过 1表示访问过，0未访问过，会动态更新
    public int[] already_arr;
    // 每个下标对应的值为前一个顶点的下标，会动态更新
    public int[] pre_visited;
    // 记录出发顶点到其他所有顶点的距离，会动态更新
    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 数组
        Arrays.fill(dis, 65535);
        // 设置出发顶点被访问过
        this.already_arr[index] = 1;
        // 设置出发顶点的访问距离为0
        this.dis[index] = 0;
    }

    // 判断index顶点是否被访问过
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

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

    // 更新pre这个顶点的前驱顶点为index顶点
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }

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

    // 继续选择并返回新的访问顶点，比如G访问后，就是A作为新的访问顶点（注意不是出发顶点）
    public int updateArr() {
        int min = 65535;
        int 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[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ") ");
            } else {
                System.out.println("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 showGraph() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

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

    // 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
    private void update(int index) {
        int len = 0;
        // 遍历matrix[index]行
        int[] ints = matrix[index];
        for (int i = 0; i < ints.length; i++) {
            // len是出发顶点到index顶点的距离+从index顶点到i顶点的距离
            len = vv.getDis(index) + ints[i];
            // 如果i顶点没有被访问过，并且len小于出发顶点到i顶点的距离，就需要更新
            if (!vv.in(i) && len < vv.getDis(i)) {
                // 更新i顶点的前驱为index顶点
                vv.updatePre(i, index);
                // 更新出发顶点到i顶点的距离
                vv.updateDis(i, len);
            }
        }
    }

    /**
     * 算法实现
     *
     * @param index 出发顶点对应的下标
     */
    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, index);
        // 更新index顶点到周围顶点的距离和前驱顶点
        update(index);
        for (int i = 0; i < vertex.length; i++) {
            // 选择并返回新的访问点
            index = vv.updateArr();
            // 更新index顶点到周围顶点的距离和前驱顶点
            update(index);
        }
    }

}

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