图解迪杰斯特拉算法（最短路径问题）_迪杰斯特拉算法求最短路径图解

一、单源最短路径问题

如上图给定一个带权图 G = <V，E>，其中每条边（vi，vj）上的权 W[vi，vj] 是一个非负实数。另外，给定 V 中的一个顶点 s 充当源点。现在要计算从源点 s 到所有其他各顶点的最短路径，这个问题通常称为单源最短路径（single-source shortest paths）问题。

用一句话总结来说，单源最短路径就是：从图的某一点（源点）出发，到达其余各顶点（终点）的最短路径。

解决单源最短路径问题的一个常用算法是迪杰斯特拉算法，它是由 E.W.Dijkstra 提出的一种按路径长度递增的次序产生到各顶点最短路径的贪心算法。

二、迪杰斯特拉算法

2.1 什么是迪杰斯特拉算法

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

迪杰斯特拉的基本思想如下：

把图的顶点集合划分为两个集合 S 和 V-S。第一个集合 S 表示距源点最短距离已经确定的顶点集，即一个顶点如果属于集合 S 则说明从源点 s 到该顶点的最短路径已知。其余的顶点放在另一个集合 V-S 中。初始时，集合 S 只包含源点，即 S = { s }，这时只有源点到自己的最短距离是已知的。设 v 是 V 中的某个顶点，把从源点 s 到顶点 v 且中间只经过集合 S 中顶点的路径称为从源点到 v 的特殊路径，并用数组 D 来记录当前所找到的从源点 s 到每个顶点的最短特殊路径长度。从尚未确定最短路径长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u，将 u 加入集合 S，同时修改数组 D 中由 s 可达的最短路径长度。

2.2 迪杰斯特拉算法的步骤

2.2.1 基本步骤

迪杰斯特拉的基本步骤如下：

1. 首先，定义一个数组 D，D[v] 表示从源点 s 到顶点 v 的边的权值，如果没有边则将 D[v] 置为无穷大。
2. 把图的顶点集合划分为两个集合 S 和 V-S。第一个集合 S 表示距源点最短距离已经确定的顶点集，即一个顶点如果属于集合 S 则说明从源点 s 到该顶点的最短路径已知。其余的顶点放在另一个集合 V-S 中。
3. 每次从尚未确定最短路径长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u，将 u 加入集合 S，同时修改数组 D 中由 s 可达的最短路径长度。若加入集合 S 的 u 作为中间顶点时，vi 的最短路特殊路径长度变短，则修改 vi 的距离值（即当D[u] + W[u, vi] < D[vi]时，令D[vi] = D[u] + W[u, vi]）。
4. 重复第 3 步的操作，一旦 S 包含了所有 V 中的顶点，D 中各顶点的距离值就记录了从源点 s 到该顶点的最短路径长度。

整个算法最核心的步骤就是第 3 步，可以将其总结为：每次从 V-S 集合中取出距离源点最近的顶点 u 加入到 S 集合中，然后更新从源点经过 u 到达各个顶点的距离。

2.2.2 图解演示

如下图所示，以 v0 为起点，演示使用迪杰斯特拉算法求解其到各个顶点的最短路径。

图解过程如下：

1. 定义一个数组 dis，dis[i] 表示从源点 v0 到顶点 vi 的边的权值，比如这里 dis[1] = 7。初始状态下，dis 各个元素为 0。

2. 定义一个集合 S 用于存放距源点最短距离已经确定的顶点。初始状态下，S = { v0 }。

   

3. 首先，以 v0 为源点，到 v1 的距离是 7，到 v2 的距离是 3，到终点的距离暂不清楚，因此假设为 ∞。此时 dis 为：

   

4. 选择最短的一条作为确定找到的最短路径。由上表可知，在 V-S 顶点集合中，v2 和源点的距离最短，因此将 v2 加入到 S 集合中。此时 S = { v0，v2 }。

   

5. 接下来我们看 V-S 中与 v2 连接的点，分别有 v3，v1。由于 dis[v2]+dis[v2_v1] < dis[v1]，故将 dis[v1] 更新为 dis[v2]+dis[v2_v1]；基于同样的理由，dis[v3] 更新为 dis[v2] + dis[v2_v3]。此时的 dis 为：

   

6. 在 V-S 的顶点集合中，v1 和源点的距离最短，因此将 v1 加入到 S 集合中，此时 S = { v0，v2，v1 }。

   

7. 接下来我们再看 V-S 中与 v1 连接的点，只有 v3 。由于 dis[v1] + dis[v1_v3] < dis[v3]，因此将 dis[v3] 更新为 dis[v1] + dis[v1_v3]。此时的 dis 为：

   

8. 再从 V-S 集合中选择距离源点最近的顶点，目前 V-S 集合中只有 v3，因此将 v3 加入到 S 集合中。此时 S = {v0，v2，v1，v3}，算法执行完毕。

   

9. 算法执行结束后，dis 数组中的值就记录了从源点到各个顶点的最短距离。

2.3 迪杰斯特拉算法的代码实现

public class DijkstraAlgorithm {

    private final static int N = 10000;     // 约定 10000 代表距离无穷大

    public static void main(String[] args) {
        char[] vertexes = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };    // 顶点
        int[][] weight = {  	// 图的邻接矩阵
                    /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/{0,   5,   7,   N,   N,   N,   2},
                /*B*/{5,   0,   N,   9,   N,   N,   3},
                /*C*/{7,   N,   0,   N,   8,   N,   N},
                /*D*/{N,   9,   N,   0,   N,   4,   N},
                /*E*/{N,   N,   8,   N,   0,   5,   4},
                /*F*/{N,   N,   N,   4,   5,   0,   6},
                /*G*/{2,   3,   N,   N,   4,   6,   0}
        };

        int source = 6; // 源点下标
        int[] dis = dijkstra(source, vertexes, weight);	// 使用迪杰斯特拉查找最短路径

        // 输出最短路径长度
        for (int i=0; i<dis.length; i++){
            System.out.println(vertexes[source] + "->" + vertexes[i] + " = " + dis[i]);
        }
    }

    /**
     * 迪杰斯特拉算法求解最短路径问题
     * @param source    源点下标
     * @param vertexes  顶点集合
     * @param weight    邻接矩阵
     * @return int[]    源点到各顶点最短路径距离
     */
    public static int[] dijkstra(int source, char[] vertexes, int[][] weight){
        int[] dis;     // 记录源点到各顶点的最短路径长度,如 dis[2] 表示源点到下标为 2 的顶点的最短路径长度
        ArrayList<Character> S = new ArrayList<>(); // 存储已经求出到源点最短路径的顶点，即算法步骤中的 S 集合。

        /* 初始化源点 */
        dis = weight[source];
        S.add(vertexes[source]);

        /* 当 S 集合元素个数等于顶点个数时，说明最短路径查找完毕 */
        while(S.size() != vertexes.length){
            int min = N;
            int index = -1; // 记录已经求出最短路径的顶点下标

            /* 从 V-S 的集合中找距离源点最近的顶点 */
            for (int j=0; j<weight.length; j++){
                if (!S.contains(vertexes[j]) && dis[j] < min){
                    min = weight[source][j];
                    index = j;
                }
            }
            dis[index] = min;   // 更新源点到该顶点的最短路径长度
            S.add(vertexes[index]); // 将顶点加入到 S 集合中，即表明该顶点已经求出到源点的最小路径

            /* 更新源点经过下标为 index 的顶点到其它各顶点的最短路径 */
            for (int m=0; m<weight.length; m++){
                if (!S.contains(vertexes[m]) && dis[index] + weight[index][m] < dis[m]){
                    dis[m] = dis[index] + weight[index][m];
                }
            }
        }
        return dis;
    }
}
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