漫画：Dijkstra 算法的优化

迷南。 2023-07-17 09:59 9阅读 0赞

在上一篇漫画中，小灰介绍了单源最短路径算法 Dijkstra，没看过的小伙伴可以看下：

[漫画：图的 “最短路径” 问题][Link 1]

漫画中我们遗留了一个问题：

**如何求得最短路径的详细节点，而不仅仅是距离？**

在本篇中，我们将会给与解答。

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

我们仍然以下面这个带权图为例，找出从顶点A到顶点G的最短距离。

![format_png 4][]

详细过程如下：

第1步，创建距离表和前置顶点表。

距离表的Key是顶点名称，Value是从起点A到对应顶点的已知最短距离，默认为无穷大；前置顶点表的Key是顶点名称，Value是从起点A到对应顶点的已知最短路径的前置定点。

![format_png 5][]

第2步，遍历起点A，找到起点A的邻接顶点B和C。从A到B的距离是5，从A到C的距离是2。把这一信息刷新到距离表当中。

同时，顶点B、C的前置顶点都是A，顶点A在邻接表中下标是0，所以把前置顶点表的B、C值更新为0：

![format_png 6][]

第3步，从距离表中找到从A出发距离最短的点，也就是顶点C。

第4步，遍历顶点C，找到顶点C的邻接顶点D和F（A已经遍历过，不需要考虑）。从C到D的距离是6，所以A到D的距离是2+6=8；从C到F的距离是8，所以从A到F的距离是2+8=10。把这一信息刷新到表中。

同时，顶点D、F的前置顶点都是C，顶点C在邻接表中下标是2，所以把前置顶点表的D、F值更新为2：

![format_png 7][]

接下来重复第3步、第4步所做的操作：

第5步，也就是第3步的重复，从距离表中找到从A出发距离最短的点（C已经遍历过，不需要考虑），也就是顶点B。

第6步，也就是第4步的重复，遍历顶点B，找到顶点B的邻接顶点D和E（A已经遍历过，不需要考虑）。从B到D的距离是1，所以A到D的距离是5+1=6，**小于距离表中的8**；从B到E的距离是6，所以从A到E的距离是5+6=11。把这一信息刷新到表中。

同时，顶点D、E的前置顶点都是B，顶点B在邻接表中下标是1，所以把前置顶点表的D、E值更新为1：

![format_png 8][]

第7步，从距离表中找到从A出发距离最短的点（B和C不用考虑），也就是顶点D。

第8步，遍历顶点D，找到顶点D的邻接顶点E和F。从D到E的距离是1，所以A到E的距离是6+1=7，**小于距离表中的11**；从D到F的距离是2，所以从A到F的距离是6+2=8，**小于距离表中的10**。把这一信息刷新到表中。

同时，顶点E、F的前置顶点都是D，顶点D在邻接表中下标是3，所以把前置顶点表的E、F值更新为3：

![format_png 9][]

第9步，从距离表中找到从A出发距离最短的点，也就是顶点E。

第10步，遍历顶点E，找到顶点E的邻接顶点G。从E到G的距离是7，所以A到G的距离是7+7=14。把这一信息刷新到表中。

同时，顶点G的前置顶点是E，顶点E在邻接表中下标是4，所以把前置顶点表的G值更新为4：

![format_png 10][]

第11步，从距离表中找到从A出发距离最短的点，也就是顶点F。

第12步，遍历顶点F，找到顶点F的邻接顶点G。从F到G的距离是3，所以A到G的距离是8+3=11，**小于距离表中的14**。把这一信息刷新到表中：

![format_png 11][]

就这样，除终点以外的全部顶点都已经遍历完毕，距离表中存储的是从起点A到所有顶点的最短距离，而前置定点存储的是从起点A到所有顶点最短路径的前置顶点。

![format_png 12][]

![format_png 13][]

如何把前置顶点表“翻译”成图的最短路径呢？我们可以使用回溯法，自后向前回溯：

第1步，找到图的终点G，它是最短路径的终点：

![format_png 14][]

第2步，通过前置定点表找到顶点G对应的前置下标5，在顶点数组中找到下标5对应的顶点F，它是顶点G的前置顶点：

![format_png 15][]

第3步，通过前置定点表找到顶点F对应的前置下标3，在顶点数组中找到下标3对应的顶点D，它是顶点F的前置顶点：

![format_png 16][]

第4步，通过前置定点表找到顶点D对应的前置下标1，在顶点数组中找到下标1对应的顶点B，它是顶点D的前置顶点：

![format_png 17][]

第5步，通过前置定点表找到顶点B对应的前置下标0，在顶点数组中找到下标0对应的顶点A，它是顶点B的前置顶点：

![format_png 18][]

如此一来，我们把前置顶点表（0,0,1,3,3,5）转化成了最短路径（A-B-D-F-G）。

![format_png 19][]

![format_png 20][]

/**
    
    * Dijkstra最短路径算法
    
    */
    
    public static int[] dijkstra(Graph graph, int startIndex) {
    
    
    
    //图的顶点数量
    
    int size = graph.vertexes.length;
    
    //创建距离表，存储从起点到每一个顶点的临时距离
    
    int[] distances = new int[size];
    
    //创建前置定点表，存储从起点到每一个顶点的已知最短路径的前置节点
    
    int[] prevs = new int[size];
    
    //记录顶点遍历状态
    
    boolean[] access = new boolean[size];
    
    
    
    //初始化最短路径表，到达每个顶点的路径代价默认为无穷大
    
    for(int i=0; i<size; i++){
    
    distances[i] = Integer.MAX_VALUE;
    
    }
    
    //遍历起点，刷新距离表
    
    access[0] = true;
    
    List<Edge> edgesFromStart = graph.adj[startIndex];
    
    for(Edge edge : edgesFromStart)
    
    {
    
    distances[edge.index] = edge.weight;
    
    prevs[edge.index] = 0;
    
    }
    
    //主循环，重复 遍历最短距离顶点和刷新距离表 的操作
    
    for(int i=1; i<size; i++)
    
    {
    
    //寻找最短距离顶点
    
    int minDistanceFromStart = Integer.MAX_VALUE;
    
    int minDistanceIndex = -1;
    
    for(int j=1; j<size; j++)
    
    {
    
    if(!access[j] && distances[j] < minDistanceFromStart)
    
    {
    
    minDistanceFromStart = distances[j];
    
    minDistanceIndex = j;
    
    }
    
    }
    
    if(minDistanceIndex == -1){
    
    break;
    
    }
    
    //遍历顶点，刷新距离表
    
    access[minDistanceIndex] = true;
    
    for(Edge edge : graph.adj[minDistanceIndex])
    
    {
    
    if(access[edge.index]){
    
    continue;
    
    }
    
    int weight = edge.weight;
    
    int preDistance = distances[edge.index];
    
    if(weight != Integer.MAX_VALUE && (minDistanceFromStart+ weight < preDistance))
    
    {
    
    distances[edge.index] = minDistanceFromStart + weight;
    
    prevs[edge.index] = minDistanceIndex;
    
    }
    
    }
    
    }
    
    
    
    return prevs;
    
    }
    
    
    
    public static void main(String[] args) {
    
    Graph graph = new Graph(7);
    
    initGraph(graph);
    
    int[] prevs = dijkstra(graph, 0);
    
    printPrevs(graph.vertexes, prevs, graph.vertexes.length-1);
    
    }
    
    
    
    private static void printPrevs(Vertex[] vertexes, int[] prev, int i){
    
    if(i>0){
    
    printPrevs(vertexes, prev, prev[i]);
    
    }
    
    System.out.println(vertexes[i].data);
    
    }
    
    
    
    /**
    
    * 图的顶点
    
    */
    
    private static class Vertex {
    
    String data;
    
    Vertex(String data) {
    
    this.data = data;
    
    }
    
    }
    
    
    
    /**
    
    * 图的边
    
    */
    
    private static class Edge {
    
    int index;
    
    int weight;
    
    Edge(int index, int weight) {
    
    this.index = index;
    
    this.weight = weight;
    
    }
    
    }
    
    
    
    /**
    
    * 图
    
    */
    
    private static class Graph {
    
    private Vertex[] vertexes;
    
    private LinkedList<Edge> adj[];
    
    
    
    Graph(int size){
    
    //初始化顶点和邻接矩阵
    
    vertexes = new Vertex[size];
    
    adj = new LinkedList[size];
    
    for(int i=0; i<adj.length; i++){
    
    adj[i] = new LinkedList<Edge>();
    
    }
    
    }
    
    }
    
    
    
    private static void initGraph(Graph graph){
    
    graph.vertexes[0] = new Vertex("A");
    
    graph.vertexes[1] = new Vertex("B");
    
    graph.vertexes[2] = new Vertex("C");
    
    graph.vertexes[3] = new Vertex("D");
    
    graph.vertexes[4] = new Vertex("E");
    
    graph.vertexes[5] = new Vertex("F");
    
    graph.vertexes[6] = new Vertex("G");
    
    
    
    graph.adj[0].add(new Edge(1, 5));
    
    graph.adj[0].add(new Edge(2, 2));
    
    graph.adj[1].add(new Edge(0, 5));
    
    graph.adj[1].add(new Edge(3, 1));
    
    graph.adj[1].add(new Edge(4, 6));
    
    graph.adj[2].add(new Edge(0, 2));
    
    graph.adj[2].add(new Edge(3, 6));
    
    graph.adj[2].add(new Edge(5, 8));
    
    graph.adj[3].add(new Edge(1, 1));
    
    graph.adj[3].add(new Edge(2, 6));
    
    graph.adj[3].add(new Edge(4, 1));
    
    graph.adj[3].add(new Edge(5, 2));
    
    graph.adj[4].add(new Edge(1, 6));
    
    graph.adj[4].add(new Edge(3, 1));
    
    graph.adj[4].add(new Edge(6, 7));
    
    graph.adj[5].add(new Edge(2, 8));
    
    graph.adj[5].add(new Edge(3, 2));
    
    graph.adj[5].add(new Edge(6, 3));
    
    graph.adj[6].add(new Edge(4, 7));
    
    graph.adj[6].add(new Edge(5, 3));
    
    }

代码中，距离表和前置顶点表都是采用数组存储，这样比较方便。

输出最短路径的时候，代码中采用了递归的方式进行回溯。

![format_png 21][]

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653197626&idx=1&sn=fca7472af006a7f8890ee84ad7cf1116&chksm=8c99e7e0bbee6ef6faa1a34160a5e135503425e37552e90dfca2fbc10f223dbf3b875e84e418&scene=21#wechat_redirect
[format_png]: /images/20230528/8a2eb4b8fc944d7e8338632039b38697.png
[format_png 1]: /images/20230528/373c164e0c1d4e149f8488968e6118ed.png
[format_png 2]: /images/20230528/7286dc5cb75d45ca9227d8c0fee86280.png
[format_png 3]: /images/20230528/c8c5d66edde34216bad3e5c1af377394.png
[format_png 4]: /images/20230528/b34833b1d99b4418abdf178a7e5506b5.png
[format_png 5]: /images/20230528/80a8bab957ad492c8dbf4588ab61f10a.png
[format_png 6]: /images/20230528/bfc3c0bf997e4209aef1576d2eeb99b9.png
[format_png 7]: /images/20230528/f8f7e826253f4c62b238d1c458a0fe3c.png
[format_png 8]: /images/20230528/4c2ba6297cb34038bc0e9bcd1c4fa32f.png
[format_png 9]: /images/20230528/bbce37e7a1f94b0993053f500cb3b207.png
[format_png 10]: /images/20230528/0916bc84ee0843f2874578ab5344f758.png
[format_png 11]: /images/20230528/fef5d2bcc93d41f4aed5607520f94deb.png
[format_png 12]: /images/20230528/f3c52bcfa92a4698abd58601bd3a66e2.png
[format_png 13]: /images/20230528/c18a4918b0514cba9449caf038c7116b.png
[format_png 14]: /images/20230528/489411696f024efa85250ceeee79e6e5.png
[format_png 15]: /images/20230528/8998e82122344e3b9643ad6ebf41d52b.png
[format_png 16]: /images/20230528/8a3c825211424535922af702d40f50b8.png
[format_png 17]: /images/20230528/6f5a5c3507e14da1a5bd6a7b3bf71e45.png
[format_png 18]: /images/20230528/f57f14d25ecb4c48850943205c957379.png
[format_png 19]: /images/20230528/c8754a0e1205440f9755d6ae1dc0d8b5.png
[format_png 20]: /images/20230528/96d34f9eee6e4b008674a96c9b0d3e27.png
[format_png 21]: /images/20230528/32d2e3db8f52491ba0cf28a9560de5c3.png