最短路径算法——迪杰斯特拉算法

回顾

上一章中，我们学了图形遍历的两种遍历方式

• 深度优先算法(DFS)
• 广度优先算法(BFS)

并且通过一个营救美女小美的案例来实现了代码。那么接着想一想，如果要营救的小美是在现实生活世界中的某个位置呢？我们怎么去很快的找到最有路径，尽快的将小美营救出来呢？

这时候使用DFS算法呢，显然不行的，我们知道DFS算法中核心逻辑是递归+回溯；上一章中营救小美案例中只有几个点，所以在递归的时候是比较快的；可是如果是在现实地图中，任意一个位置都是一个点，这么多点，如果在使用DFS算法，只能压死电脑了。既然DFS行不通。那么我们就要改用其他算法了——迪杰斯特拉算法。

最短路径分析

最短路径问题分析

在计算最短路径的时候，首先需要我们解决的是怎么把图形结构存储起来。这里我们很容易可以想到

• 线性数据结构(数组+链表)
• 非线性数据结构(树+图)

我们要求地图中的最短路径，肯定是要用图形结构来存储，并且要用图形结构中的有向图存储。

问题转换

我们可以把地图中的几个重要的点转换到图形结构中，那么每条路的长度就是图形中边的权重。这时候可以得到如下图形结构：

如果1作为起点，我们要到6去，那么这个问题就被转换成了求点1到点6的最短路径。

算法思路分析

数据结构分析

由上一章中我们知道，存储图形数据结构有两种方法：

• 邻接矩阵(二维数组)
• 邻接表(链表)

这两种存储方式的选择：

一般情况下，如果数据量比较大，那么选择使用邻接表(链表)来存储；如果数据量不大，使用领接矩阵(二维数组)来存储

这里我们是做案例数据比较少，选择使用领接矩阵(二维数组)来存储。

算法选择

这次使用迪杰斯特拉算法，就是单源最短路径算法，他是所有最短路径算法的基础，我们的地图软件最终使用的算法都是以这个算法为基础优化来的。所以这个算法很重要

迪杰斯特拉算法思想

迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。从局部最优推出全局最优

需要明确的几个关键变量

1、dis数组： 用来表示起始点到每个顶点的距离，最开始这个数组中的值是无穷大，赋值最大求最小；

举例：如果起始点是1

(1) dis[1]: 从顶点1到顶点1的距离为dis[1]

(2) dis[2]: 从顶点1到顶点2的距离为dis[2]

(3) dis[3]: 从顶点1到顶点3的距离为dis[3]

……

因为在图1中共有6个点，且我们的下标从1开始，所以数组地宁弈的长度应该是dis[7]，即dis[n+1]

2、loc变量： 用来赋值当前走的是第几个顶点，初始的时候需要将其赋值为初始点，这里我们的初始点为1，所以赋值为1

3、data[][]： 二维数组，表示领接矩阵，用来存储图形结构

例如：

(1) data[1][1]: 顶点1到顶点1的距离是data[1][1]

(2) data[1][2]: 顶点1到顶点2的距离是data[1][2]

(3) data[1][2]: 顶点1到顶点3的距离是data[1][3]

核心思路

1. 创建一个dis数组，用来表示起始点到每个顶点的距离，最开始的时候我们将其赋值为无穷大
2. 创建data[][]数组，用来存储图之间点与点的关系，边的距离
3. 定义变量loc，初始赋值为起始点，用来存储当前操作的点的索引，当前是第几个顶点
4. 使用贪心的策略，先取dis数组中最小的值，也就是取dis数组中距离起始点最近的权重的点
5. 将loc赋值为当前取出的点的索引，判断当前这个点可以到的其他点的路径长度，更新dis数组中的值。
6. 注意，dis数组中已经选取过的点我们不能再次进行选择了
7. 重复步骤4、5操作，知道所有的点都处理完毕

图解分析

如上图所示，我们需要创建一个6*6的二维数组来保存图中节点关系。为了方便数组操作，我们二维数组的下标都从1开始，所以我们这里创建7*7的二维数组。如下图：

最短路径长度求解

1、初始化dis数组：

2、以结点“1”作为初始点，初始化dis数组，取loc=1，将dis[loc]进行标记，被标记后的结点，在下次取结点的时候是不可以取的。

• dis[1]: 表示结点“1”到结点“1”的距离，因为结点“1”是我们的起始节点，所以距离是0
• dis[2]: 表示结点“1”到结点“2”的距离，因为图中结点“1”到结点“2”没有边相连接，即data[1][2] = -1，所以dis[2] = MAX
• dis[3]: 表示结点“1”到结点“3”的距离，因为图中结点“1”到结点“3”有边相连接，即data[1][3] = 10，所以dis[3] = 10
• dis[4]: 表示结点“1”到结点“4”的距离，因为图中结点“1”到结点“4”没有边相连接，即data[1][4] = -1，所以dis[4] = MAX
• dis[5]: 表示结点“1”到结点“5”的距离，因为图中结点“1”到结点“5”有边相连接，即data[1][5] = 30，所以dis[5] = 30
• dis[6]: 表示结点“1”到结点“6”的距离，因为图中结点“1”到结点“6”有边相连接，即data[1][6] = 100，所以dis[6] = 100

3、从dis数组中选取未被标记的且路径权重最小的结点 ，这时候dis数组中最小的结点是“3”，所以取loc = 3，且标记dis[loc],即dis[3]，下次取结点是该结点不能被取到。

从图1中可以看出结点“3”到一条边是可以到结点“4”，且权重是50，即data[3][4] = 50；所以dis数组中结点“1”到结点“4”的距离更新为min(dis[4],dis[3] + data[3][4]),这个公式很重要，当前的loc=3，也就是当前我们观察结点“3”，当我们的结点“3”加进来的时候，我们的结点“3”是可以到达结点“4”的，所以我们现在比较的是我们保存的结点“1”->结点“3”的最小距离（dis[3]）加上结点“3”到结点“4”的距离(data[3][4])大，还是结点“1”直接到结点“4”的距离(dis[4])大，然后将距离小的更新到dis[4]中；即 min(MAX,10+50=60)，60 远小于MAX，所以更新dis[4] = 60;

以上这个操作就是松弛操作

4、从dis数组中选取未被标记的且路径权重最小的结点 ，这时候dis数组中最小的结点是“5”，所以取loc = 5，且标记dis[loc]，即dis[5]；下次取结点是该结点不能被取到。

这里选取的结点是loc=5，以结点“5”为起点可以到达结点“4”和结点“6”两个方向。

• 首先来看从结点“5”到结点“4”：权重是20，即data[5][4] = 20，所以这里dis[4]路径权重是结点“1”到结点“5”的路径权重加结点“5”到结点“4”的路径权重，即dis[5] + data[5][4] = 30+20=50，小于当前dis[4]中MAX，所以更新dis[4] = 50;
• 再看从结点“5”到结点“6”：权重是60，即data[5][6] = 60，同样这里dis[6]的路径权重是结点“1”到结点“5”的路径权重加结点“5”到结点“6”的路径权重，即dis[5] + data[5][6] = 30+60=90，小于当前dis[6]中的100，所以更新dis[6] = 90

5、从dis数组中选取未被标记的且路径权重最小的结点 ，这时候dis数组中最小的结点是“4”，所以取loc = 4，且标记dis[loc]，即dis[4]；下次取结点是该结点不能被取到。

结点“4”可以到结点“6”，所以dis[6] = dis[4] + data[4][6] = 50 + 10 = 60，小于当前dis[6]中的90，所以更新dis[6] = 60

6、从dis数组中选取未被标记的且路径权重最小的结点 ，这时候dis数组中最小的结点是“6”，所以取loc = 6，且标记dis[loc]，即dis[6]；下次取结点是该结点不能被取到。

此时没有进行更新操作，因为结点“6”不能够到达任何一个结点

7、从dis数组中选取未被标记的且路径权重最小的结点 ，这时候dis数组中最小的结点是“2”，所以取loc = 2，且标记dis[loc]，即dis[2]；下次取结点是该结点不能被取到。

结点“2”可以到达结点“3”，路径权重是5，但是从结点“1”是无法到达结点“2”，所以dis[3] = dis[2] + data[2][3] = MAX + 5 结果是小于dis[2]中MAX，所以这里不更新

8、截止到这里数组遍历完毕，此时dis中的数据存放的就是起点到各个点的最短路径。

最短路径分析

我们将每一次dis的变化以及当前的loc代表的节点标注起来。

需要明确一点，我们最后的dis数组一定保存的是起始点距离其下标(即某个结点)的最短路径。起始点我们是结点“1”

(1) dis[1]: 表示结点“1”到结点“1”的最短路径

(2) dis[2]: 表示结点“1”到结点“2”的最短路径

……

通过这种方式我们最后得到的是起点到所有节点的最短路径，因此我们需要一个Map集合来保存最终的所有的起始点可以到达的所有结点的最短路径，然后每一个结点对应着一个列表或者栈来保存路径

1、当loc = 1的时候，我们改变的是结点“1”,结点“3”,结点“5”,结点“6”对应的dis数组下标的值，所以从起始点“1”到结点“1”,结点“3”,结点“5”,结点“6”的最短路径为：

这里的最短路径是指从起始结点“1”可以直接到终止节点的最短路径且路径长度不为MAX,所以这里就是表示从起始节点“1”到结点“3”、“5”、“6”的最短路径

2、当loc = 3的时候，我们改变的是结点“4”对应的dis数组下标的值，所以从起始点“1”到结点“4”的最短路径为：

这里我们改变了结点“4”的最短路径，即dis数组中下标为4的最短路径值。根据前面推出的最短路径的公式**min(dis[x],data[x][loc] + dis[x])** ，因为我们当前loc = 3，所以可以得知，dis[4] > dis[3] + data[3][4]，所以才会将dis[4]的最短路径长度改成60(结点“1”到结点“3”的最短路径长度为10 + 结点“3”到结点“4”的路径长度50)，所以要保存的最短路径可以是map.get(3).push(4),即map.get(loc).push(i),然后将这个路径放在map中，其中map的key是i，这里就是放置在map中，key为4

3、当loc = 5的时候，我们改变的是结点“4”、6对应的dis数组下标的值，所以从起始点“1”到结点“4”，“6”的最短路径为：

这里的路径是利用**map.get(loc).push(i)得到的，这里的loc = 5,i = 4,6** ，我们再处理完之后再将其重新复制给map中key为4和6的。

4、当loc = 4的时候，我们改变的是结点“6”对应的dis数组下标的值，所以从起始点“1”到结点“6”的最短路径为：

这个路径是利用**map.get(loc).push(i)得到的，这里loc = 4，i = 6** ，我们再处理完之后再将其重新赋值给map中key为6的

5、当loc = 6的时候，我们没有改变任何dis数组中的值，所以各个结点的最短路径不会发生更新

……后面情况类似不再分析，如果和上一步没有发生改变则不会去更改其最短路径

总结

我们的dis数组中保存的值就是我们认为截止到当前loc点为止，我们认为的最短的路径；min(dis[loc] + data[loc][x],dis[x])这个公式的意思就是取我们认为的起点到loc的最短路径加上loc到x的路径和起点到x的最短路径做比较，取最小值，将其更新到dis[x]中

代码实现

如上图所示，求结点1到结点6的最短路径：

(1) 输出最短路径经过的所有结点

(2) 输出最短路径的长度

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

package com.lhb.test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author 92823
 * 迪杰斯特拉求最短的路径
 */
public class MinRoute {
    public static void main(String[] args) {
        // n表示点数，即当前图中有多少个顶点
        int n;
        // m表示当前这个图有多少个边（为了方便我们一会构造图）
        int m;
        // begin表示我们的起点，即我们从哪一个点开始进行运算
        int begin;

        // 接受用户的输入
        Scanner cin = new Scanner(System.in);
        // 赋值点数，边数，起点
        n = cin.nextInt();
        m = cin.nextInt();
        begin = cin.nextInt();

        // 声明邻接矩阵, 因为我们的下标都是从0开始，所以长度都要加1，有几个点就是维度是几的二维数组
        int data[][] = new int[n + 1][n + 1];
        // 用来存取起点到下标的最短路径，因为下标还是从1开始的，所以长度还是需要加一，dis[5]就表示起点到顶点5的最短距离
        int dis[] = new int[n + 1];
        // 初始化一个Map，因为最后我们求出来的dis是起点到左右点的最短距离
        Map<Integer, Stack<Integer>> routeMap = new HashMap<>();
        // 初始化dis数组和邻接矩阵二维数组data[][]
        // 下标从1开始，所以有n个点，我们就要操作到第n个元素
        for (int i = 1; i <= n; i++) {
            // 初始化dis数组，因为求最短路径，所以dis中存的应该是最大值
            dis[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                // 赋值我们的二维数组，就是赋值邻接矩阵
                // 初始化邻接矩阵都是-1，-1表示的是顶点之间没有联系
                data[i][j] = -1;
                // 如果是自己和自己，则将其长度设置为0
                if (i == j) {
                    data[i][j] = 0;
                }
            }
        }

        // 赋值邻接矩阵，哪个点与哪个点有值，在此赋值
        for (int i = 0; i < m; i++) {
            // 横坐标
            int x = cin.nextInt();
            // 纵坐标
            int y = cin.nextInt();
            // 点与点之间的距离
            int value = cin.nextInt();
            // 表示的是xx到yy的距离是vv
            data[x][y] = value;

            // 如果当前的横坐标等于我们规定的起始位置下标
            if (x == begin) {
                // 直接赋值dis的第一次，即当loc为起点的时候，dis数组的值，dis[i]表示起点到i的值
                // 赋值起点到y的值为value，默认情况都是MAX
                dis[y] = value;
                // 赋值初始值
                Stack<Integer> stack = new Stack<>();
                // 将起点也就是路径走的第一步赋值进去
                stack.push(begin);
                // 赋值终点
                stack.push(y);
                routeMap.put(y, stack);
            }
        }
        // 开始搜索最短路径，起点begin，最短路径的dis数组（表示起点到其下标的点的最短路径），data表示的是邻接矩阵，n表示总共有多少个顶点
        search(begin, dis, data, n, routeMap);
        routeMap.forEach((key,path)->{
            System.out.println("从结点"+ begin +"到结点" + key + "的最短路径为: " + dis[key] + "， 最短路径规划为：" + path.toString());
        });
    }

    /**
     * 开始搜索最短路径
     * @param begin 起始点
     * @param dis 最短路径数组
     * @param data 邻接矩阵
     * @param n 表示有多少个顶点
     * @param routeMap 走的最短路径的点
     */
    private static void search(int begin, int[] dis, int[][] data, int n, Map<Integer, Stack<Integer>> routeMap) {
        // 标记数组，用来表示dis中哪一个值已经被标记了，标记过的无需再次处理, 下标从1开始，所以需要长度是n+1
        boolean mark[] = new boolean[n + 1];
        // 起点已经赋值过了 所以将起点标注为true 表示已经赋值过了
        mark[begin] = true;
        // 当前节点到当前节点的最短路径是0
        dis[begin] = 0;
        // 循环遍历数组
        int index = 1;
        // 我们最多就是找节点的次数（n）
        while (index <= n) {
            // loc用来表示当前的节点
            int loc = 0;
            // 用于记录当前的dis中存储的最小值
            int min = Integer.MAX_VALUE;
            // 遍历dis数组，找到当前dis最小的
            for (int i = 1; i <= n; i++) {
                // 如果当前的dis中的点没有被标记，且小于我们的最小值
                if (!mark[i] && dis[i] < min) {
                    // 保存最小值和其下标
                    min = dis[i];
                    loc = i;
                }
            }
            // 表示没有找到最小的或者全都被标记了，此时我们退出循环
            if (loc == 0) {
                break;
            }
            // 将当前的loc点进行标记
            mark[loc] = true;
            // 拿到当前顶点对应的 最短路径的取法
            Stack<Integer> stack = routeMap.get(loc);
            // 更新dis数组，就是我们的dis[loc] + data[loc][X] 是否小于 dis[X] 若小于更新dis[X]的值
            for (int i = 1; i <= n; i++) {
                if (data[loc][i] != -1 && (dis[loc] + data[loc][i] < dis[i])) {
                    // 更新dis数组的值
                    dis[i] = dis[loc] + data[loc][i];
                    // 拷贝一份 因为直接改会影响
                    Stack<Integer> stackClone = (Stack<Integer>)stack.clone();
                    // 将当前的新的节点放进去
                    stackClone.push(i);
                    // 将其放入map中
                    routeMap.put(i, stackClone);
                }
            }
            // 下标加1
            index ++;
        }
    }
}

• 输入：

  1 2 3 4 5 6 7 8 9 10 11

  6 8 1 1 3 10 1 5 30 1 6 100 2 3 5 3 4 50 4 6 10 5 4 20 5 6 60

• 输出结果：

  1 2 3 4

  从结点1到结点3的最短路径为: 10， 最短路径规划为：[1, 3] 从结点1到结点4的最短路径为: 50， 最短路径规划为：[1, 5, 4] 从结点1到结点5的最短路径为: 30， 最短路径规划为：[1, 5] 从结点1到结点6的最短路径为: 60， 最短路径规划为：[1, 5, 4, 6]

  如果起点和部分顶点没有边，则不会打印

小结

1. 地图软件就是基于迪杰斯特拉算法进行实现的，采用了A*启发式搜索算法，但是其根本算法还是通过迪杰斯特拉算法改进优化而来的。
2. 如果我们的地图很大，可以缩小计算范围，只画出一部分区域。如果是省之间的，则没必要加很细粒度的点，绘画出大的省区，然后计算完之后，在计算省内的，几个大点，最后一级一级的推出来。
3. 本节课计算最短路径的时候一定要明白递推公式**min(dis[loc] + data[loc][x], dis[s])** ，其中dis是我们的起点到各个结点的最短路径长度的数组，loc是我们当前操作的结点索引，x表示当前的结点(loc)到x结点是有边的。