最短路径的概念

最短路径的问题是比较典型的应用问题。在图中，确定了起始点和终点之后，一般情况下都可以有很多条路径来连接两者。而边或弧的权值最小的那一条路径就称为两点之间的最短路径，路径上的第一个顶点为源点，最后一个顶点为终点。

图的最短路径的算法有很多，本文主要介绍狄克斯特拉（Dijkstra）提出的一种按照长度递增的次序产生的最短路径的算法。

 

Dijkstra算法介绍

Dijkstra算法的特点

Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的时间复杂度是n的平方，可以使用堆优化。

但是，要注意一点，Dijkstra算法只能适用于权值为正的情况下；如果权值存在负数，则不能使用。

Dijkstra算法的思想

1. 设置两个顶点集S和T，集合S中存放已经找到最短路径的顶点，集合T中存放着当前还未找到最短路径的顶点；
2. 初始状态下，集合S中只包含源点V1，T中为除了源点之外的其余顶点，此时源点到各顶点的最短路径为两个顶点所连的边上的权值，如果源点V1到该顶点没有边，则最小路径为无穷大；
3. 从集合T中选取到源点V1的路径长度最短的顶点Vi加入到集合S中；
4. 修改源点V1到集合T中剩余顶点Vj的最短路径长度。新的最短路径长度值为Vj原来的最短路径长度值与顶点Vi的最短路径长度加上Vi到Vj的路径长度值中的较小者；
5. 不断重复步骤3、4，直至集合T的顶点全部加入到集合S中。

Dijkstra算法的实例演示

下面求下图，从源点v1到其他各个顶点的最短路径：

首先第一步，我们先声明一个dis数组（这是一个距离数组，用于记录各点距离源点的距离），该数组初始化的值为： 

我们的顶点集T的初始化为：T={v1}。

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 

为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短。

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果：

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： 

然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图： 

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： 

因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

起点  终点    最短路径    长度
v1    v2     无          ∞    v3     {v1,v3}    10v4     {v1,v5,v4}  50v5     {v1,v5}    30v6     {v1，v5,v4,v6} 60

由此分析下来，我们可以得到以下几点：

1、需要设立两个数组，一个数组为diatance，用于存放个顶点距离源点的距离；另一个数组为st，用于判断顶点是在哪一个集合内（true为在S集合，false为在T集合内）。

2、Dijkstra算法的精髓：

• 每次循环都将T集合内距离源点最近的那个点加入到S集合中，且加入的那个点距离源点的距离由“最短距离估计值”转变成“最短距离准确值”；
• 每次循环添加一个点到S集合中后，会导致与加入的那个点相邻的顶点可能会发生距离的更新，也就是“最短距离估计值”的更新。更新方法是取原本的“最短距离估计值”与新加入的那个点的“最短距离确定值”+新加入的那个点与其邻点的距离的较小者。
• “最短距离估计值”的真正内涵：其实可以把S集合看成一个黑箱子，“最短距离估计值”就是该顶点经过黑箱子里的各个点到源点的最短距离，但不能保证该顶点是否可以通过黑箱子外（T集合）的顶点绕路达到更短。只有每次循环中“最短距离估计值”中的最小值，才能确定为“最短距离确定值”加入到集合S。

 

Dijkstra算法的Java代码实现

基于邻接矩阵的代码实现：

	public int[] dijkstra(int v) {if (v < 0 || v >= numOfVexs)throw new ArrayIndexOutOfBoundsException();boolean[] st = new boolean[numOfVexs];// 默认初始为falseint[] distance = new int[numOfVexs];// 存放源点到其他点的矩离for (int i = 0; i < numOfVexs; i++)for (int j = i + 1; j < numOfVexs; j++) {if (edges[i][j] == 0) {edges[i][j] = Integer.MAX_VALUE;edges[j][i] = Integer.MAX_VALUE;}}for (int i = 0; i < numOfVexs; i++) {distance[i] = edges[v][i];}st[v] = true;// 处理从源点到其余顶点的最短路径for (int i = 0; i < numOfVexs; ++i) {int min = Integer.MAX_VALUE;int index=-1;// 比较从源点到其余顶点的路径长度for (int j = 0; j < numOfVexs; ++j) {// 从源点到j顶点的最短路径还没有找到if (st[j]==false) {// 从源点到j顶点的路径长度最小if (distance[j] < min) {index = j;min = distance[j];}}}//找到源点到索引为index顶点的最短路径长度if(index!=-1)st[index] = true;// 更新当前最短路径及距离for (int w = 0; w < numOfVexs; w++)if (st[w] == false) {if (edges[index][w] != Integer.MAX_VALUE&& (min + edges[index][w] < distance[w]))distance[w] = min + edges[index][w];}}return distance;}

基于邻接表的代码实现：

	public int[] dijkstra(int v) {if (v < 0 || v >= numOfVexs)throw new ArrayIndexOutOfBoundsException();boolean[] st = new boolean[numOfVexs];// 默认初始为falseint[] distance = new int[numOfVexs];// 存放源点到其他点的距离for (int i = 0; i < numOfVexs; i++) {distance[i] = Integer.MAX_VALUE;}ENode current;current = vexs[v].firstadj;while (current != null) {distance[current.adjvex] = current.weight;current = current.nextadj;}distance[v] = 0;st[v] = true;// 处理从源点到其余顶点的最短路径for (int i = 0; i < numOfVexs; i++) {int min = Integer.MAX_VALUE;int index = -1;// 比较从源点到其余顶点的路径长度for (int j = 0; j < numOfVexs; j++) {// 从源点到j顶点的最短路径还没有找到if (st[j] == false) {// 从源点到j顶点的路径长度最小if (distance[j] < min) {index = j;min = distance[j];}}}// 找到源点到索引为index顶点的最短路径长度if (index != -1)st[index] = true;// 更新当前最短路径及距离for (int w = 0; w < numOfVexs; w++)if (st[w] == false) {current = vexs[w].firstadj;while (current != null) {if (current.adjvex == index)if ((min + current.weight) < distance[w]) {distance[w] = min + current.weight;break;}current = current.nextadj;}}}return distance;}

关于算法程序的两点说明：

1. 这边方法一个参数是表明了源点的位置，方法的内部会找出从源点到图中每个点的路径最小值；
2. 这边的其他的主要部分（如成员变量的定义等），参考【数据结构】图（邻接矩阵、邻接表）的JAVA代码实现。