数据结构与算法(32): 图- 单源最短路径Dijkstra

发表于   |   分类于

  迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
  Dijkstra算法每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

算法的基本思想：

  1. 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
  2. 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
  3. 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。
    3.1. 然后，从U中找出路径最短的顶点k，并将其加入到S中；
    3.2. 接着，利用3.1中选出的顶点k更新U中的顶点和顶点对应的路径，例如(s,v)的距离可能大于(s,k)+(k,v)的距离；
    3.3. 重复3.1~3.2操作，直到遍历完所有顶点。

使用邻接矩阵实现的时间复杂度为$O(V^2)$，使用邻接表实现的复杂度为$O(E+V)\log{V}$

缺点：Dijkstra算法求最短路径的图是不能有负权边的，因为扩展到负权边的时候会产生更短的路程，有可能就破坏了已经更新的点路程不会改变的性质。

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
	public class Dijkstra {
    public static void main(String[] args) {
        int[][] edges = {{0, 1, 2}, {0, 2, 6}, {0, 3, 4}, {1, 2, 3}, {2, 0, 7}, {2, 3, 1}, {3, 0, 5}, {3, 2, 12}};
        int vlen = 4;
        int elen = edges.length;
        int[][] e = new int[vlen][vlen];
        int inf = 9999;
        // true: 已知起点到该点的最短路径; false: 未知起点到该点的最短路径
        boolean[] booked = new boolean[vlen];
        // 存储起点到个顶点的最短路程的“估计值”
        int[] dis = new int[vlen];
        // 初始化 边的权重矩阵
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                if (i == j){
                    e[i][j] = 0;
                }else {
                    e[i][j] = inf;
                }
            }
        }
        // 读入边
        for (int i = 0; i < elen; i++){
            e[edges[i][0]][edges[i][1]] = edges[i][2];
        }
        // 初始化dis, 起始顶点为0号顶点; 初始化booked数组
        for (int i = 0; i < vlen; i++){
            dis[i] = e[0][i];
            booked[i] = false;
        }
        booked[0] = true;
        // Dijkstra算法核心语句
        // 除去起点, 需要确定n-1个顶点到起点的最短路径
        int u = 0;
        for (int i = 0; i < vlen - 1; i ++){
            int min = inf;
            // 找到离起点最近的顶点
            for (int j = 0; j < vlen; j++){
                if (!booked[j] && dis[j] < min){
                    min = dis[j];
                    u = j;
                }
            }
            // 标记"顶点u"为已经获取到最短路径
            booked[u] = true;
            // 修正dis
            for (int v = 0; v < vlen; v++){
                if (dis[v] > dis[u] + e[u][v]){
                    dis[v] = dis[u] + e[u][v];
                }
            }
        }
        // 输出结果
        for (int d: dis){
            System.out.print(d + " ");
        }
    }
}

结果为：

1
0 2 5 4