Dijkstra算法

引言

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运行过一次之后，通过从目的节点回溯的方法，得到整个路径。用伪代码表示其思想如下：

1Dijkstra
2    set the route weight of vertice as  infinity;
3    set initial vertex's route weight as 0;
4    add initial vertex to fringeSet;
5
6    while(not every vertex are processed) do
7        select the minimize route weight vertex v from fringeSet;
8        remove v from fringeSet;
9        
10        for each neighbor nbr of v do
11            update nbr's route weight;
12            update nbr's last vertex;
13            if nbr not in fringeSet then
14                add nbr to fringeSet;
15            end if 
16        end for
17        
18        add v to processedSet;
19    end while

JAVA实现

鄙人自己实现了一版：

1 1 package com.structures.graph;
2 2 
3 3 import com.structures.linear.Stack;
4 4 import java.util.ArrayList;
5 5 
6 6 /**
7 7  * Created by wx on 2018/1/9.
8 8  * Implement of Dijkstra algorithm.
9 9  */
1010 public class Dijkstra<T> {
1111     private final static int MAX_WEIGHT = Integer.MAX_VALUE;
1212     private ArrayList<Vertex<T>> graph;     //图的邻接链表
1313     private ArrayList<Vertex<T>> processedVertex;   //已处理顶点
1414     private ArrayList<Integer> fringeVertex;    //边缘顶点
1515 
1616     private int[] routeWeight;              //路径长度
1717     private int[] lastNodeIndex;            //存放其在最优路径中的上个顶点索引
1818 
1919 
2020     public Dijkstra(myGraph<T> newGraph){
2121         graph = newGraph.getVerList();
2222         initializeWeight();
2323         lastNodeIndex = new int[graph.size()];
2424         processedVertex = new ArrayList<Vertex<T>>();
2525         fringeVertex = new ArrayList<Integer>();
2626     }
2727 
2828     // 初始化路径长度值
2929     private void initializeWeight(){
3030         routeWeight = new int[graph.size()];
3131         for(int i=0; i<routeWeight.length; i++)
3232             routeWeight[i] = MAX_WEIGHT;
3333     }
3434 
3535     // 默认顶点数组第一个元素为起始元素
3636     // 四件事，记录最小路径，记录上个顶点，记录已处理顶点，记录边缘顶点
3737     public void dijkstra(){
3838         int curIndex = 0;
3939         routeWeight[0] = 0;
4040         fringeVertex.add(curIndex);
4141 
4242         while(processedVertex.size() < graph.size()){   //此处条件也可以是fringeVertex.size()>0
4343             curIndex = getNextIndex(); //在边缘顶点集合中找到路径长度最小的顶点的索引
4444             fringeVertex.remove((Integer) curIndex);
4545 
4646             for(Neighbor nbr : graph.get(curIndex).neighbors){  //更新到邻居顶点的最短路径
4747 
4848                 if(!processedVertex.contains(graph.get(nbr.index))){
4949                     weightNeighbor wnbr = (weightNeighbor)nbr;
5050 
5151                     if (routeWeight[curIndex] + wnbr.weight < routeWeight[wnbr.index]) {
5252                         lastNodeIndex[nbr.index] = curIndex;   //更新上个顶点
5353                         routeWeight[nbr.index] = routeWeight[curIndex] + wnbr.weight;  //选择较小的值保存
5454                     }
5555 
5656                     if (!fringeVertex.contains(nbr.index))
5757                         fringeVertex.add(nbr.index);
5858                 }
5959             }
6060             processedVertex.add(graph.get(curIndex));
6161         }
6262     }
6363 
6464     //选出下个路径计算起点
6565     private int getNextIndex(){
6666         int nextIndex = fringeVertex.get(0);
6767         for(int i=1; i<fringeVertex.size(); i++){
6868             int index = fringeVertex.get(i);
6969             if(routeWeight[index]<routeWeight[nextIndex])
7070                 nextIndex = index;
7171         }
7272         return nextIndex;
7373     }
7474 
7575     // 逆向回溯输出路径，并返回最大路径长度
7676     int findMinRoute(int finalIndex){
7777         Stack<Integer> route = new Stack<Integer>();
7878         int curIndex = finalIndex;
7979         route.push(curIndex);
8080 
8181         while(curIndex!=0){   //将沿途顶点压栈
8282             curIndex = lastNodeIndex[curIndex];
8383             route.push(curIndex);
8484         }
8585 
8686         System.out.print("The minimize weight route is ");
8787         while(!route.isEmpty()){    //通过出栈达到反向输出的目的
8888             System.out.print(route.pop());
8989             if(route.size()!=0)
9090                 System.out.print("→");
9191         }
9292         System.out.print(".\n");
9393 
9494         return routeWeight[finalIndex];
9595     }
9696 }

经测试，表现良好。

Dijkstra后续

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

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

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

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