稀有猿诉

十年磨一剑，历炼出锋芒，说话千百句，不如码二行。

Understanding Dijkstra Algorithm

最短路径问题，是图论中经常遇到的问题，对于非加权图，用广度优先搜索（BFS）就可以找到两个顶点之间的最短路径（最少边数），但对于加权图，就需要用到著名的犾克斯特拉算法（Dijkstra Algorithm）。

思路

犾克斯特拉算法的核心思想是：

  1. 以起步的顶点作为当前顶点
  2. 检查当前顶点的所有邻接顶点，计算当前顶点到所有其邻接顶点的权重，并记录下来
  3. 从未访问过的邻接顶点中，选择一个总权重最小的顶点，作为下一个当前顶点
  4. 重复第3步，直到图中所有的顶点都被访问过

这样就能得到起步顶点到其他所有顶点的最短路径（最小权重）。

实例

前面的思路听起来还是不够清爽，我们来看一个具体的实例，比如计算不同的城市之间的飞行费用问题，就可以用Dijkstra算法来求解，一共有五个城市，以及它们之间的航班费用：

flowchart LR; A([Atlanta]) B([Boston]) C([Chicago]) D([Denver]) E([El Paso]) A-- 100 -->B; A-- 160 -->D; B-- 120 -->C; B-- 180 -->D; D-- 40 -->C; D-- 140 -->E;

以Atlanta为起点，来计算到其他几个城市的最小飞行费用，为方便用一个表格来展现Dijkstra算法的每一步：

步骤 当前顶点 Atlanta Boston Chicago Denver El Paso 说明
初始化 n/a inf inf inf inf inf inf为正无穷，代表还未有计算的距离
第1步
起始顶点作为当前顶点 		Atlanta 0 100 inf 160 inf Atlanta能到达Boston和Denver，是邻接 的顶点 直接填权重
第2步
未访问顶点Boston和Denver中选择权重小的Boston 		Boston 0 100 220 160 inf 到Boston的费用是100，以此为基础，
Boston到Chicago是120，所以起始点到Chicago的费用是220。
Boston到Denver是180再加上基础100就是280，它大于Atlanta直飞Denver，所以这个放弃
第3步
未访问的中Denver最小，所以用Denver 		Denver 0 100 200 160 300 到Denver的费用是160，以此为基础，
Denver到Chicago是40，经Denver到Chicago更划算，所以到Chicago更新为200；
Denver还可以到达El Paso费用是300
第4步
未访问的中Chicago最小，所以用Chicago 		Chicago 0 100 200 160 280 到Chicago的费用是200，以此为基础，
Chicago到El Paso是80，经Chicago到El Paso更划算，所以到El Paso更新为280
第5步
只有El Paso未访问了，所以用El Paso 		El Paso 0 100 200 160 280 到El Paso的费用是280，以此为基础，
El Paso到Boston是100，不划算，所以不用更新。
所有顶点都访问过了，这就是Atlanta出发到所有城市的最小飞行费用

实现

Dijkstra算法比较复杂，它的时间空间复杂度都比较高。算法的输入是一个加树图，和一个起始顶点，输出则是一个列表，表示起始顶点到其他顶点的最短路径。

实现思路

  1. 创建一个结果列表，长度是顶点数量N，尽管其实不管起始顶点，但为了方便还是加上，用以存储起始顶点到所有顶点的最小距离，列表初始化为正无穷
  2. 创建一个标记列表，长度是N，用以标记顶点是否访问过，在选择下一个当前节点时，以及判断算法是否结束时，都需要用到此列表
  3. 选择实始顶点为当前顶点
  4. 把当前节点加入到标记列表中
  5. 更新最小距离列表：以当前顶点为基础，计算到它的每个邻接顶点的距离（也即基础值加上与其邻接的边的权重），如果距离小于结果列表中的距离，就更新结果列表
  6. 选择下一个当前顶点：遍历结果列表，找最小值，并且还未访问过（不在标记列表里），作为下一个当前顶点
  7. 重复第4到第6步，直到所有顶点都已标记，这时在第6步肯定 找不到下一个当前顶点

伪代码

有了前面的实现思路，就不难写出伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

creat a list with length of N distanceList, init with MAX
create a set visitedSet
currentNode = start
distanceList[start] = 0
while currentNode is not null:
    add currentNode to visitedSet
    
    base = distanceList[currentNode]
    for each node adjacent with currentNode:
         if node.weight + base < distanceList[node]:
              distanceList[node] = node.weight + base
              
    min = null
    for each node in distanceList:
        if node not in visitedSet and min > distanceList[node]:
              min = node;
    currentNode = min

示例代码

到了代码层面的实现，需要灵活选择数据结构，如果顶点可以方便的用下标来代表的话，那么就可以用数组代替列表，否则可能就要使用哈希表。这里为了方便，用下标来代表顶点：0代表Atlanta，1代表Boston，2代表Chicago，3代表Denver，4代表El Paso，这样就都可以用数组来当列表用。

图用矩阵来表示，每一行代表到另一个城市的费用，其实默认值可以都用0，在计算费用时就不用特殊处理了，但为了体现邻接顶点，所以没有连通的顶点用-1，自己用0，相邻的顶点才有权重。

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

public class DijkstraAlgorithm {
    public static int[] dijkstra(int[][] graph, int start) {
        final int n = graph.length;
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        Arrays.fill(visited, false);
        distance[start] = 0;
        int current = start;
        while (current != -1) {
            // Mark as current node as visited
            visited[current] = true;

            // Update the shortest distance for the nodes adjacent with current node
            final int base = distance[current];
            int[] neighbors = graph[current];
            for (int i = 0; i < n; i++) {
                if (neighbors[i] == -1) {
                    // Skip not adjacent node
                    continue;
                }
                if (base + neighbors[i] < distance[i]) {
                    distance[i] = base + neighbors[i];
                }
            }

            // Pick next current node
            int min = -1;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && (min == -1 || distance[min] > distance[i])) {
                    min = i;
                }
            }

            current = min;
        }

        return distance;
    }

    public static void main(String[] args) {
        String[] cities = {"Atlanta", "Boston", "Chicago", "Denver", "El Paso"};
        int[][] graph = {
                {0, 100, -1, 160, -1},
                {-1, 0, 120, 180, -1},
                {-1, -1, 0, -1, 80},
                {-1, -1, 40, 0, 140},
                {-1, 100, -1, -1, 0},
        };
        int start = 0;
        int[] shortestPath = dijkstra(graph, start);
        IntStream.range(start + 1, graph.length)
                .mapToObj(i -> "Shortest distance from " + cities[start] + " to " + cities[i] + ": " + shortestPath[i])
                .forEach(System.out::println);
    }
}

输出结果：

1
2
3
4

Shortest distance from Atlanta to Boston: 100
Shortest distance from Atlanta to Chicago: 200
Shortest distance from Atlanta to Denver: 160
Shortest distance from Atlanta to El Paso: 280

应用

Dijkstra算法只能用于有向无环加权图（DAG），且没有负权重的情况下，才可以正常工作。并且，它的复杂度较高，如果顶点数量为n，那么它的时间复杂度会达到O(n2)。

参考资料

Comments