最短路径问题——迪杰斯特拉算法(Dijkstra)

曾经终败给现在 2021-06-10 20:38 453阅读 0赞

前段时间看到一篇文章，里面提到了统治世界的十大算法，其中之一就是迪杰斯特拉算法（Dijkstra），该算法主要解决的”最短路径“这一类问题。说法虽然夸张了点，但它在实际生活中确实应用广泛，例如地图软件等，大部分游戏中自动寻路等功能，使用到的 A\*搜索算法也是基于迪杰斯特拉算法优化而来。那么迪杰斯特拉算法是如何实现的呢？

假如我们现在有如下一个有向图，图中有 6 个顶点，编号分别为 1~6，带有箭头的直线表示的是能从一个顶点到达另外一个顶点，直线上的数字表示的是两个顶点之间的距离，现在求顶点 1 到顶点 6 的最短距离。

![format_png][]

由于图中的点比较少，我们直接手动计算就能算出来这个结果，但是如果顶点很多，有成千上万个，手动计算就很难了，我们只能通过程序来计算，那么我们的程序该如何写呢？

### 思路 ###

从图中我们可以看到，顶点 1 只能直接到达顶点 2、3、5，不能直接到达顶点 6，所以要想从 1 到达 6，就必须得从其他顶点中转。

我们定义一个数组，用来表示每个顶点到顶点 1 的距离，数组的索引表示的是顶点编号，数组元素的值表示的是到顶点 1 的最小距离。

1.  开始我们在顶点 1 上，顶点 1 能到达 2、3、5，数组的状态如下。
    
    <table> 
     <thead> 
      <tr> 
       <th>索引</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>最小距离</td> 
       <td>0</td> 
       <td>60</td> 
       <td>10</td> 
       <td>null</td> 
       <td>50</td> 
       <td>null</td> 
      </tr> 
     </tbody> 
    </table>
2.  从顶点 2 处中转，顶点 2 能到达顶点 4，距离为 35，所以顶点 1 到顶点 4 的距离为 60+35=95，数组状态如下：

1.  从顶点 3 处中转，顶点 3 能到达 4，距离为 30。如果通过顶点 3 中转，那么 1 到达 4 的距离为 40，小于经过 2 中转的距离，所以数组中到顶点 4 的距离更新为 40。顶点 3 还能到达顶点 5，同理，通过顶点 2 中转，1 到达 5 的距离为 10+25=35，小于 1 直接到达 5 的距离，因此数组中到达顶点 5 的距离更新为 35，更新后，数组状态如下：

1.  从顶点 5 中转，顶点 5 能到达 2，如果顶点 1 通过顶点 5 到达 2，距离为 35+30=65，大于顶点 1 直接到达 2，所以不更新。由于顶点 2 在前面已经遍历过它能到达哪些点了，所以后面不需要再遍历它。顶点 5 还能到达顶点 6，所以此时 1 到达 6 的距离为 35+105=140，数组状态如下：

1.  从顶点 4 中转，顶点 4 也能达到顶点 6。如果通过顶点 4 中转，那么 1 到达 6 的距离为 40+15=55，这个距离小于从 5 中转，所以更新数组，更新后，数组状态如下：

以上流程，就是迪杰斯特拉算法在计算最短路径问题时的核心流程。

### 代码实现 ###

首先我们需要将这个有向图用代码表示出来，通常表示图的方法有两种：第一种是邻接矩阵（也就是二维数组），第二种是邻接表（也就是数组+链表），这里我们选用邻接表法来表示一个有向图。

另外我们还需要定义顶点之间的边，一条边有起点和终点，还有边的权重信息，也就是长度，用类 Edge 表示。代码如下：

private class Edge {
        // 起始定点
        public int s;
        // 终止定点
        public int t;
        // 边的权重
        public int weight;
    
        Edge(int s, int t, int weight) {
            this.s = s;
            this.t = t;
            this.weight = weight;
        }
    }

有向图我们用类 Graph 表示，类中有两个属性：顶点个数 v 和描述顶点之间边的信息的数组 adj，我们还提供了一个方法：addEdge，用来在两个顶点之间添加一条边。代码如下：

public class Graph {
    
        // 顶点个数（顶点编号从0开始，在本文例子中，编号为0的顶点不存在）
        private int v;
    
        // 记录每个顶点的边
        private LinkedList<Edge>[] adj;
    
        public Graph(int v) {
            this.v = v;
            // 初始化
            this.adj = new LinkedList[v];
            for (int i = 0; i < v; i++) {
                adj[i] = new LinkedList();
            }
        }
    
        // 添加一条边，从s到达t
        public void addEdge(int s, int t, int weight) {
            Edge edge = new Edge(s, t, weight);
            adj[s].add(edge);
        }
    }

定义好了图的描述信息后，接下来通过代码来实现迪杰斯特拉算法，其代码和注释如下。

有两处逻辑稍微解释一下。第一处：flag 数组记录的是已经遍历过的顶点，用来防止死循环，例如顶点 1 能到达 2，我们接着会判断 2 能到达哪些点，顶点 1 又能到达 5，5 也能到达 2，如果没有 flag 数组来记录顶点 2 我们已经遍历过了，那么我们就会继续遍历 2，这样会导致死循环。第二处：predecessor 数组记录的是路径信息，数组的索引表示的顶点编号，元素的值表示的是哪一个顶点到达当前顶点的，例如：predecessor\[3\]=1 表示的是通过顶点 1 到达的顶点 3。

// 采用迪杰斯特拉算法找出从s到t的最短路径
    public void dijkstra(int s, int t) {
        int[] dist = new int[v];    // 记录s到每个顶点的最小距离，数组下标表示顶点编号，值表示最小距离
        boolean[] flag = new boolean[v];    // 记录遍历过的顶点，数组下标表示顶点编号，值表示是否遍历过该顶点
        for (int i = 0; i < v; i++) {
            dist[i] = Integer.MAX_VALUE;    // 初始状态下，将顶点s到其他顶点的距离都设置为无穷大
        }
        int[] predecessor = new int[v];     // 记录路径，索引表示顶点编号，值表示到达当前顶点的顶点是哪一个
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        dist[s] = 0;    // s->s的路径为0
        while (!queue.isEmpty()) {
            Integer vertex = queue.poll();
            if (flag[vertex]) continue; // 已经遍历过该顶点，就不再遍历
            flag[vertex] = true;
            for (int i = 0; i < adj[vertex].size(); i++) {
                Edge edge = adj[vertex].get(i);
                if (dist[vertex] < (dist[edge.t] - edge.weight)) {  // 如果出现了比当前路径小的方式，就更新为更小路径
                    dist[edge.t] = dist[vertex] + edge.weight;
                    predecessor[edge.t] = vertex;
                }
                queue.add(edge.t);
            }
        }
        // 打印路径
        System.out.println("最短距离：" + dist[t]);
        System.out.print(s);
        print(s, t, predecessor);
    }

print 函数的作用是打印从顶点 s 到达顶点 t 的最短路径中，需要经过哪些点，具体代码如下，就是一个递归调用，比较简单：

// 打印路径
    private void print(int s, int t, int[] predecessor) {
        if (t == s) {
            return;
        }
        print(s, predecessor[t], predecessor);
        System.out.print(" -> " + t);
    }

### 测试 ###

根据文中的示例，构建一个图，进行结果测试，代码如下：

public static void main(String[] args) {
        // 构建图
        Graph graph = new Graph(7);
        graph.addEdge(1, 2, 60);
        graph.addEdge(1, 3, 10);
        graph.addEdge(1, 5, 50);
        graph.addEdge(2, 4, 35);
        graph.addEdge(3, 4, 30);
        graph.addEdge(3, 5, 25);
        graph.addEdge(4, 6, 15);
        graph.addEdge(5, 2, 30);
        graph.addEdge(5, 6, 105);
        // 计算最短距离
        graph.dijkstra(1, 6);
    }

测试结果：

![format_png 1][]

### 总结 ###

迪杰斯特拉算法的思想与广度优先搜索（BFS）的思路比较像，每次找到自己能到达的顶点，然后依次往外扩散，直到遍历完所有顶点。

[format_png]: /images/20210527/0fe9a75dfa90437c81e341c2742a8f98.png
[format_png 1]: /images/20210527/c8ef03adcc5f4932ade4317aaa206b20.png