引言

Dijkstra算法主要应用在寻找带正边权的图中顶点之间的最短路径。这种例子在生活中非常多，比如导航软件自动规划路径，路径最短或用时最少的路径总是作为最优路径返回给你；又比如我大天朝最常见的找人办事，有的时候我们没法直接找到可以帮忙的人，就需要再找别人帮忙，又或者关系不够铁，找人花的代价很大，我们总是潜意识里找关系最铁并中转最少的人去帮忙。

算法原理

先上图：

这个图比较简单，换个复杂的图就没那么容易看了。不过，我们关注策略，用什么图举例没差。现在目的即 要找到从A到F的最短路径，我们先不看这个问题。先看从A到C，C是A的邻居，在BFS算法中第一波就可以访问得到。但是A直接到C是最短路径吗？不然，用肉眼就能看出A→B→E→C的路径更短。从B出发有可能找到比A→C更短的路径，因为 len(AB)<len(AC)，而从C出发是一定找不到更短的路径。这个用反证法很容易就能得到。简单写一下Dijkstra算法的步骤：

• 第一步，遍历A的邻居，记录其邻居顶点到达路径长度。将其邻居放入边缘顶点集合中。
• 第二步，从边缘集合中找到路径长度最短的顶点并返回之。
• 第三步，从第二步中返回的顶点出发，访问其邻居顶点并将其加入边缘顶点集合，如果到达邻居的路径长度小于之前路径长度，则更新邻居顶点路径。返回第二步，直至边缘顶点集合为空结束。

只写了三步，不是很严谨，请见谅。需要注意的是，图中的顶点在算法中被分成了三个部分，未访问过的顶点，边缘顶点，访问过的顶点。像访问A的时候B和C就成了边缘顶点，其余是未访问顶点。而访问B的时候D和E加入了边缘顶点集合，现在边缘顶点集合包括C D E,而B成了访问过顶点。

如何记录从始发点到各个顶点的路径？不需要记录整条路径，只记录其在最短路径中的上个顶点就可以了，在Dijkstra运行过一次之后，通过从目的节点回溯的方法，得到整个路径。用伪代码表示其思想如下：

Dijkstra
    set the route weight of vertice as  infinity;
    set initial vertex's route weight as 0;
    add initial vertex to fringeSet;

    while(not every vertex are processed) do
        select the minimize route weight vertex v from fringeSet;
        remove v from fringeSet;
        
        for each neighbor nbr of v do
            update nbr's route weight;
            update nbr's last vertex;
            if nbr not in fringeSet then
                add nbr to fringeSet;
            end if 
        end for
        
        add v to processedSet;
    end while

JAVA实现

鄙人自己实现了一版：

 1 package com.structures.graph;
 2 
 3 import com.structures.linear.Stack;
 4 import java.util.ArrayList;
 5 
 6 /**
 7  * Created by wx on 2018/1/9.
 8  * Implement of Dijkstra algorithm.
 9  */
10 public class Dijkstra<T> {
11     private final static int MAX_WEIGHT = Integer.MAX_VALUE;
12     private ArrayList<Vertex<T>> graph;     //图的邻接链表
13     private ArrayList<Vertex<T>> processedVertex;   //已处理顶点
14     private ArrayList<Integer> fringeVertex;    //边缘顶点
15 
16     private int[] routeWeight;              //路径长度
17     private int[] lastNodeIndex;            //存放其在最优路径中的上个顶点索引
18 
19 
20     public Dijkstra(myGraph<T> newGraph){
21         graph = newGraph.getVerList();
22         initializeWeight();
23         lastNodeIndex = new int[graph.size()];
24         processedVertex = new ArrayList<Vertex<T>>();
25         fringeVertex = new ArrayList<Integer>();
26     }
27 
28     // 初始化路径长度值
29     private void initializeWeight(){
30         routeWeight = new int[graph.size()];
31         for(int i=0; i<routeWeight.length; i++)
32             routeWeight[i] = MAX_WEIGHT;
33     }
34 
35     // 默认顶点数组第一个元素为起始元素
36     // 四件事，记录最小路径，记录上个顶点，记录已处理顶点，记录边缘顶点
37     public void dijkstra(){
38         int curIndex = 0;
39         routeWeight[0] = 0;
40         fringeVertex.add(curIndex);
41 
42         while(processedVertex.size() < graph.size()){   //此处条件也可以是fringeVertex.size()>0
43             curIndex = getNextIndex(); //在边缘顶点集合中找到路径长度最小的顶点的索引
44             fringeVertex.remove((Integer) curIndex);
45 
46             for(Neighbor nbr : graph.get(curIndex).neighbors){  //更新到邻居顶点的最短路径
47 
48                 if(!processedVertex.contains(graph.get(nbr.index))){
49                     weightNeighbor wnbr = (weightNeighbor)nbr;
50 
51                     if (routeWeight[curIndex] + wnbr.weight < routeWeight[wnbr.index]) {
52                         lastNodeIndex[nbr.index] = curIndex;   //更新上个顶点
53                         routeWeight[nbr.index] = routeWeight[curIndex] + wnbr.weight;  //选择较小的值保存
54                     }
55 
56                     if (!fringeVertex.contains(nbr.index))
57                         fringeVertex.add(nbr.index);
58                 }
59             }
60             processedVertex.add(graph.get(curIndex));
61         }
62     }
63 
64     //选出下个路径计算起点
65     private int getNextIndex(){
66         int nextIndex = fringeVertex.get(0);
67         for(int i=1; i<fringeVertex.size(); i++){
68             int index = fringeVertex.get(i);
69             if(routeWeight[index]<routeWeight[nextIndex])
70                 nextIndex = index;
71         }
72         return nextIndex;
73     }
74 
75     // 逆向回溯输出路径，并返回最大路径长度
76     int findMinRoute(int finalIndex){
77         Stack<Integer> route = new Stack<Integer>();
78         int curIndex = finalIndex;
79         route.push(curIndex);
80 
81         while(curIndex!=0){   //将沿途顶点压栈
82             curIndex = lastNodeIndex[curIndex];
83             route.push(curIndex);
84         }
85 
86         System.out.print("The minimize weight route is ");
87         while(!route.isEmpty()){    //通过出栈达到反向输出的目的
88             System.out.print(route.pop());
89             if(route.size()!=0)
90                 System.out.print("→");
91         }
92         System.out.print(".\n");
93 
94         return routeWeight[finalIndex];
95     }
96 }

经测试，表现良好。

Dijkstra后续

网上对Dijkstra算法有一些争议，最主要的就是：

• 它到底是贪心算法还是动态规划？

其实这两者不是互斥的，在Dijkstra算法中，我们看到了贪心的策略，即每次选择可到达路径最短的顶点作为下次迭代的起始顶点。也看到了BFS遍历的性质，即以路径长度为BFS遍历的依据，一层一层往外遍历。同样看到了动态规划的思想，重复子问题，最优子结构，无后效性。

说实话，动态规划自己理解得也不是很到位，虽然做过一些例子，像最简单的01背包问题，地图上寻找两个城市的最短路径，HMM里的Viterbi算法。但总觉得有一层雾，非常朦胧。还记得当年上算法课，黄刘生老师给我们讲过，“贪心算法比较简单，但是动态规划就比较难了，像笨一点的人就写不出来。” 可能这也是激励我后来思考动态规划的一个原因，哈哈。本来想在本文结尾处写一下动态规划的东西，但实在是火候不够，先mark一下，等我觉得差不多了，再补上！