DijkstraAlgorithm(迪杰斯特拉算法)

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

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

最短路径

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径，大致可以分为如下几种问题，可无论如何分类问题，其本质思想还是不变的，即，求两点间的最短距离。

a) 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。

b) 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

c) 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。

d) 全局最短路径问题 - 求图中所有的最短路径。

迪杰斯特拉(Dijkstra)算法概述

如上图，迪杰斯特拉算法的核心思路是：

1. 指定一个节点，例如我们要计算 ‘A’ 到其他节点的最短路径

2. 引入三个集合（dis，already_arr，pre_visited），dis集合包含已求出的最短路径的点（以及相应的最短长度），already_arr 记录各个顶点是否被访问过 (1 表示访问过,0 未访问)会动态更新， pre_visited 每个下标对应的值为前一个顶点下标, 会动态更新

3. 初始化三个集合，already_arr集合初始时 只有当前节点要设置为已访问（即already_arr[index] = 1）

4. dis集合初始时为 A->A = 0 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞

5. 从还没访问的节点中找出路径最短的点，加入dis集合，例如 A->D = 2

6. 更新already_arr 和 pre_visited 集合路径，if ( ‘D 到 B,C,E 的距离’ + ‘AD 距离’ < ‘A 到 B,C,E 的距离’ ) 则更新already_arr 和 pre_visited 集合

7. 循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

迪杰斯特拉算法应用场景-最短路径问题

1. 战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到A, B, C , D, E, F 六个村庄

2. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里

3. 问：如何计算出 G 村庄到 其它各个村庄的最短距离?

4. 如果从其它点出发到各个点的最短距离又是多少?

代码实现

public class DijkstraAlgorithm {
    // 表示不连通
    public static final int INF = 65535;
    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int[][] matrix = new int[vertexs.length][vertexs.length];
        matrix[0]= new int[]{INF, 5, 7, INF, INF, INF, 2};
        matrix[1]= new int[]{5, INF, INF, 9, INF, INF, 3};
        matrix[2]= new int[]{7, INF, INF, INF, 8, INF, INF};
        matrix[3]= new int[]{INF, 9, INF, INF, INF, 4, INF};
        matrix[4]= new int[]{INF, INF, 8, INF, INF, 5, 4};
        matrix[5]= new int[]{INF, INF, INF, 4, 5, INF, 6};
        matrix[6]= new int[]{2, 3, INF, INF, 4, 6, INF};

        // 创建Graph对象
        Graph graph = new Graph(vertexs, matrix);
        graph.showGraph();
		//要开始寻找的顶点下标
        int index = 6;
        graph.dijkstra(index);
        graph.showDijkstra(index);
    }
}

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

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

    // 显示结果
    public void showDijkstra(int index) {
        vv.print(index);
    }

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

    // dijkstra 算法
    public void dijkstra(int index) {
        vv = new VistedVertex(vertex.length, index);
        // 更新 index 下标顶点到周围顶点的距离和周围顶点的前驱顶点
        update(index);
        for (int j = 1; j < vertex.length; j++) {
            // 选择并返回新的访问顶点
            index = vv.updateArr();
            // 更新 index 下标顶点到周围顶点的距离和周围顶点的前驱顶点
            update(index);
        }
    }

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

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

    /**
     * 构造器
     * @param length 顶点的个数
     * @param index 出发顶点对应的下标 eg: G -> 6
     */
    public VistedVertex(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, DijkstraAlgorithm.INF);
        // 设置出发顶点已被访问过
        this.already_arr[index] = 1;
        // 设置出发顶点的访问距离为 0
        this.dis[index] = 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) {
        this.dis[index] = len;
    }

    /**
     * 更新 pre 顶点的前驱为 index 顶点
     * @param pre 当前前驱顶点对应的下标
     * @param index 要更新的前驱顶点对应的下标
     */
    public void updatePre(int pre, int index) {
        this.pre_visited[pre] = index;
    }

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

    // 继续选择并返回新的访问顶点
    // 比如这里的 G 完后，就是 A 点作为新的访问顶点(注意不是出发顶点)
    public int updateArr() {
        int min = DijkstraAlgorithm.INF;
        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 print(int index) {
        System.out.println("\nalready_arr==========================");
        for (int i : already_arr) {
            System.out.print(i + " ");
        }
        System.out.println("\npre_visited==========================");
        for (int i : pre_visited) {
            System.out.print(i + " ");
        }
        System.out.println("\ndis==================================");
        for (int i : dis) {
            System.out.print(i + " ");
        }
        System.out.println();
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int count = 0;
        for (int i : dis) {
            if (i != DijkstraAlgorithm.INF) {
                System.out.print(vertexs[index] + "->" + vertexs[count] + "的距离：" + i + "\t");
            } else {
                System.out.println("INF");
            }
            count++;
        }
    }
}
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

运行结果

从G点开始

从A点开始

从B点开始

注：以上大部分内容来源于韩顺平老师的数据结构和算法笔记