前言

部分内容摘自程杰的《大话数据结构》

1. 最短路径

  我们时常会面临着对路径选择的决策问题。例如在北京、上海、 广州等城市，因其城市面积较大，乘地铁或公交都要考虑从A点到B点，如何换乘到达？比如下图这样的地铁网图，如果不是专门去做研究，对于刚接触的人来说，都会犯迷糊。
  现实中，每个人需求不同，选择方案就不尽相同。有人为了省钱，它需要的是路程最短（定价以路程长短为标准），但可能由于线路班次少，换乘站间距离长等原因并不省时间；而另一些人，为了要赶飞机火车或者早晨上班不迟到，他最大的需求是总时间要短；还有一类人，如老人行动不便，或者上班族下班，忙碌一天累得要死， 他们都不想多走路，哪怕车子绕远路耗时长也无所谓，关键是换乘要少，这样可以在车上好好休息一下（有些线路方案换乘两次比换乘三四次耗时还长）。这些都是老百姓的需求，简单的图形可以靠人的经验和感觉，但复杂的道路或地铁网就需要计算机通过算法计算来提供最佳的方案。我们今天就要来研究关于图的最短路径的问题。
  在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。显然，我们研究网图更有实际意义，就地图来说，距离就是两顶点间的权值之和。而非网图完全可以理解为所有的边的权值都为 1 的网。
  我们要讲解两种求最短路径的算法。先来讲第一种， 从某个源点到其余各顶点的最短路径问题。
  你能很快计算出下图中由源点 v0_0 到终点 v8_8 的最短路径吗？如果不能，没关系，我们一同来研究看如何让计算机计算出来。

1.1 迪杰斯特拉（Dijkstra）算法

  这是一个按路径长度递增的次序产生最短路径的算法。它的思路大体是这样的。
  比如说要求下图中顶点 v0_0 到顶点 v1_1 的最短距离，没有比这更简单的了，答案就是 1，路径就是直接 v0_0 连线到 v1_1。
  由于顶点 v1_1 还与 v2_2、v3_3、v4_4 连线，所以此时我们同时求得了 v0_0→v1_1→v2_2=1+3=4，v0_0→v1_1→v3_3=1+7=8，v0_0→v1_1→v4_4=1+5=6。
  现在，我问 v0_0 到 v2_2 的最短距离，如果你不假思索地说是 5，那就犯错了。因为边上都有权值，刚才已经有 v0_0→v1_1→v2_2 的结果是 4，比 5 还要小 1 个单位，它才是最短距离，如下图所示。
  由于顶点 v2_2 还与 v4_4、v5_5 连线，所以此时我们同时求得了 v0_0→v2_2→v4_4 其实就是 v0_0→v1_1→v2_2→v4_4=4+1=5，v0_0→v2_2→v5_5=4+7=11.这里 v0_0→v2_2 我们用的是刚才计算出来的较小的 4。此时我们也发现 v0_0→v1_1→v2_2→v4_4=5 要比 v0_0→v1_1→v4_4=6 还要小。所以 v0_0 到 v4_4 目前的最小距离是 5，如下图所示。
  当我们要求 v0_0 到 v3_3 的最短距离时，通向 v3_3 的三条边，除了 v6_6 没有研究过外，v0_0→v1_1→v3_3 的结果是 8，而 v0_0→v4_4→v3_3=5+2=7。因此，v0_0 到 v3_3 的最短距离是 7，如下图所示。
  好了，我想你大致明白，这个迪杰斯特拉（Dijkstra）算法是如何干活的了。它并不是一下子就求出了 v0_0 到 v8_8 的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。
  如果还是不太明白，不要紧，现在我们来看代码，从代码的模拟运行中，再次去理解它的思想。
  先来看看数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef struct
{
	int vexs[MAXVEX];
	int arc[MAXVEX][MEXVEX];
	int numVertexes, numEdges;
}MGraph;

typedef int Pathmarc[MAXVEX];		/* 用于存储最短路径下标的数组 */
typedef int ShortPathTable[MAXVEX1;	/* 用于存储到各点最短路径的权值和 */

  算法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* Dijkstra算法，求有向网G的V0顶点到其余顶点v最短路径P[V]及带权长度D[v] */
/* P[v]的值为前驱顶点下标，D[v]表示V0到v的最短路径长度和 */
void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatirx *P,
ShortPathTable *D)
{
	int v,w,k,min;
	int final[MAXVEX];	/* final[w]=1表示求得顶点v0至vw的最短路径 */
	for (v=0; v<G.numVertexes; v++)	/* 初始化数据 */
	{
		final[v] = 0;	/* 全部顶点初始化为未知最短路径状态 */
		(*D)[v] = G.matirx[v0][v];	/* 将与v0点有连线的顶点加上权值 */
		(*P)[v] = -1;	/* 初始化路径数组P为-1 */
	}
	(*D)[v0] = 0;	/* v0至V0路径为0 */
	final[vo] = 1;	/* v0至v0不需要求路径*/
	/* 开始主循环，每次求得V0到某个v顶点的最短路径*/
	for (v=1; v<G.numVertexes; v++)
	{
		min=INFINITY;	/* 当前所知离v0顶点的最近距离 */
		for(w=0; w<G.numVertexes; w++)	/* 寻找离v0最近的顶点 */
		{
			if(!finaltw] && (*D)[w]<min)
			{
				k=w;
				min = (*D)[w];	/* w顶点离V0顶点更近 */
			}
		}
		final[k] = 1;	/* 将目前找到的最近的顶点置为1 */
		for (w=0; w<G.numVertexes; w++)	/* 修正当前最短路径及距离 */
		{
			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
			if(!final[w] && (min+G.matirx[k][w]<(*D)[w]))
			{	/* 说明找到了更短的路径，修改D[w]和P[w] */
				(*D)[w] = min + G.matirx[k][w];	/* 修改当前路径长度 */
				(*P)[w]=k;
			}
		}
	}
}

  调用此函数前，其实我们需要为左下图准备邻接矩阵MGraph的G，如右下图，并且定义参数 v0_0 为 0。

  1. 程序开始运行，第 6 行final数组是为了 v0_0 到某顶点是否已经求得最短路径的标记，如果 v0_0 到 vw_w 已经有结果，则final[w]=1。
  2. 第 7~12 行，是在对数据进行初始化的工作。此时final数组值均为 0，表示所有的点都未求得最短路径。D数组为{65535,1,5,65535,65535,65535,65535,65535,65535}。因为 v0_0 与 v1_1 和 v2_2 的边权值为 1 和 5。P数组全为 0，表示目前没有路径。
  3. 第 13 行，表示 v0_0 到 v0_0 自身，权值和结果为 0。D数组为 {0,1,5,65535,65535,65535,65535,65535,65535}。第 14 行，表示 v0_0 点算是已经求得最短路径，因此final[0]=1。此时final数组为 {1,0,0,0,0,0,0,0,0}。 此时整个初始化工作完成。
  4. 第 16~37 行，为主循环，每次循环求得 v0_0 与一个顶点的最短路径。因此v从 1 而不是 0 开始。
  5. 第 18~26 行，先令min为 65535 的极大值，通过w循环，与D[w]比较找到最小值min=1，k=1。
  6. 第 27 行，由k=1，表示与 v0_0 最近的顶点是 v1_1，并且由D[1]=1，知道此时 v0_0 到 v1_1 的最短距离是 1。因此将 v1_1 对应的final[1]设置为 1。此时final数组为{1,1,0,0,0,0,0,0,0}。
  7. 第 28~36 行是一循环，此循环甚为关键。它的目的是在刚才已经找到 v0_0 与 v1_1 的最短路径的基础上，对 v1_1 与其他顶点的边进行计算，得到 v0_0 与它们的当前最短距离，如下图所示。因为min=1，所以本来D[2]=5，现在 v0_0→v1_1→v2_2=D[2]=min+3=4，v0_0→v1_1→v3_3=D[3]=min+7=8，v0_0→v1_1→v4_4=D[4]=min+5=6，因此，D数组当前值为 {0,1,4,8,6,655535,65535,65535,65535}。而P[2]=1，P[3]=1，P[4]=1，它表示的意思是 v0_0 到 v2_2、v3_3、v4_4 点的最短路径它们的前驱均是 v1_1。此时P数组值为：{-1,-1,1,1,1,-1,-1,-1,-1}。
  8. 重新开始循环，此时i=2。第 18~26 行，对w循环，注意因为final[0]=1和final[1]=1，由第 21 行的!final[w]可知，v0_0 与 v1_1 并不参与最小值的获取。通过循环比较，找到最小值min=4，k=2。
  9. 第 27 行，由k=2，表示已经求出 v0_0 到 v2_2 的最短路径，并且由D[2]=4，知道最短距离是 4。因此将 v2_2 对应的final[2]设置为 1，此时final数组为：{1,1,1,0,0,0,0,0,0}。
  10. 第 28~36 行。在刚才已经找到 v0_0 与 v2_2 的最短路径的基础上，对 v2_2 与其他顶点的边，进行计算，得到 v0_0 与它们的当前最短距离，如下图所示。因为min=4，所以本来D[4]=6，现在v0_0→v2_2→v4_4=D[4]=min+1=5，v0_0→v2_2→v5_5=D[5]=min+7=11，因此，D数组当前值为：{0,1,4.8.5,11,65535,65535,65535}。而原本P[4]=1，此时P[4]=2，P[5]=2，它表示 v0_0 到 v4_4、v5_5 点的最短路径它们的前驱均是 v2_2。此时P数组值为：{-1,-1,1,1,2,2,-1,-1,-1}。
  11. 重新开始循环，此时v=3。 第 17~23 行，通过对w循环比较找到最小值min=5，k=4。
  12. 第 27 行，由k=4，表示已经求出 v0_0 到 v4_4 的最短路径，并且由D[4]=5，知道最短距离是 5。因此将 v4_4 对应的final[4]设置为 1。此时final数组为：{1,1,1,0,1,0,0,0,0}.
  13. 第 28~36 行。对 v4_4 与其他顶点的边进行计算，得到 v0_0 与它们的当前最短距离，如下图所示。因为min=5， 所以本来D[3]=8，现在v0_0→v4_4→v3_3=D[3]=min+2=7，本来D[5]=11，现在v0_0→v4_4→v5_5=D[5]=min+3=8，另外v0_0→v4_4→v6_6=D[6]=min+6=11，v0_0→v4_4→v7_7=D[7]=min+9=14，因此，D数组当前值为：{0,1,4,7,5,11,14,65535}。 而原本P[3]=1，此时P[3]=4，原本P[5]=2，此时P[5]=4，另外P[6]=4，P[7]=4，它表示 v0_0 到 v3_3、v5_5、 v6_6、v7_7点的最短路径它们的前驱均是 v4_4。此时P数组值为：{-1,-1,1,4,2,4,4,4,-1}。
  14. 之后的循环就完全类似了。得到最终的结果，如下图所示。此时final数组为：{1,1,1,1,1,1,1,1,1}，它表示所有的顶点均完成了最短路径的查找工作。此时D数组为：{0,1.4,7,5.,8,10,12,16}，它表示 v0_0 到各个顶点的最短路径数，比如D[8]=1+3+1+2+3+2+4=16。此时的P数组为：{-1,-1,1,4,2,4.3,6,7}，这串数字可能略为难理解一些。比如P[8]=7，它的意思是 v0_0 到 v8_8 的最短路径，顶点 v8_8 的前驱项点是 v7_7，再由P[7]=6表示 v7_7 的前驱是 v6_6，P[6]=3，表示 v6_6 的前驱是 v3_3。这样就可以得到，v0_0到 v8_8 的最短路径为 v8_8← v7_7← v6_6← v3_3← v4_4← v2_2← v1_1← v0_0，即v0_0→v1_1→v2_2→v4_4→v3_3→v6_6→v7_7→v8_8。

  其实最终返回的数组D和数组P，是可以得到 v0_0 到任意一个顶点的最短路径和路径长度的。例如 v0_0 到 v8_8 的最短路径并没有经过 v5_5，但我们已经知道 v0_0 到 v5_5 的最短路径了。由D[5]=8可知它的路径长度为 8，由P[5]=4可知 v5_5 的前驱顶点是 v4_4，所以 v0_0 到 v5_5 的最短路径是 v0_0→v1_1→v2_2→v4_4→v5_5。
  也就是说，我们通过迪杰斯特拉（Dijkstra）算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以很容易得到此算法的时间复杂度为 O(n2)O(n^2)，尽管有同人觉得，可不可以只找到从源点到某一个特定终点的最短路径，其实这个问题和求源点到其他所有顶点的最短路径一样复杂， 时间复杂度依然是 O(n2)O(n^2)。
  这就好比，你吃了七个包子终于算是吃饱了，就感觉很不划算，前六个包子白吃了，应该直接吃第七个包子，于是你就去寻找可以吃一一个就能饱肚子的包子，能够满足你的要求最终结果只能有一个， 那就是用七个包子的面粉和馅做的一个大包子。这种只关注结果而忽略过程的思想是非常不可取的。
  可如果我们还需要知道如 v3_3 到 v5_5、v1_1 到 v7_7 这样的任一顶点到其余所有顶点的最短路径怎么办呢？此时简单的办法就是对每个顶点当作源点运行一次迪杰斯特拉（Dijksra）算法，等于在原有算法的基础上，再来一次循环， 此时整个算法的时间复杂度就成了 O(n3)O(n^3)。
  对此，我们现在再来介绍另一个求最短路径的算法——弗洛伊德（Floyd），它求所有顶点到所有顶点的时间复杂度也是O(n3)O(n^3)，但其算法非常简洁优雅，能让人感觉到智慧的无限魅力。好了，让我们就一同来欣赏和学习它吧。

1.2 佛洛依德（Floyd）算法

  为了能讲明白弗洛伊德（Floyd）算法的精妙所在，我们先来看最简单的案例。左下图是一个最简单的 3 个顶点连通网图。

  我们先定义两个二维数组D[3][3]和P[3][3]，D代表顶点到顶点的最短路径权值和的矩阵。P代表对应顶点的最小路径的前驱矩阵。在未分析任何顶点之前，我们将D命名为 D−1D^{-1}，其实它就是初始的图的邻接矩阵。将P命名为 P−1P^{-1}，初始化为图中所示的矩阵。
  首先我们来分析，所有的顶点经过 v0_0 后到达另一顶点的最短路径。因为只有三个顶点，因此需要查看 v1_1→v0_0→v2_2，得到D−1D^{-1}[1][0]+D−1D^{-1}[0][2]=2+1=3。D−1D^{-1}[1][2]表示的是 v1_1→v2_2 的权值为 5，我们发现 D−1D^{-1}[1][2]>D−1D^{-1}[1][0]+D−1D^{-1}[0][2]，通俗的话讲就是 v1_1→v0_0→v2_2 比直接 v1_1→v2_2 距离还要近。所以我们就让 D−1D^{-1}[1][2]=D−1D^{-1}[1][0]+D−1D^{-1}[0][2]=3，同样的D−1D^{-1}[2][1]=3， 于是就有了 D0D^{0} 的矩阵。因为有变化，所以P矩阵对应的 P−1P^{-1}[1][2] 和 P−1P^{-1}[2][1] 也修改为当前中转的顶点 v0_0 的下标 0，于是就有了 P0P^{0}。 也就是说

D0[v][w]=min{D−1[v][w],D−1[v][0]+D−1[0][w]}D^0[v][w]=min\{D^{-1}[v][w],D^{-1}[v][0]+D^{-1}[0][w]\}

  接下来，其实也就是在 D0D^{0} 和 P0P^{0} 的基础上继续处理所有顶点经过 v1_1 和 v2_2 后到达另一顶点的最短路径，得到 D1D^{1} 和 P1P^{1}、D2D^{2} 和 P2P^{2} 完成所有顶点到所有顶点的最短路径计算工作。
  如果我就用这么简单的图形来讲解代码，大家一定会 觉得不能说明什么问题。所以我们还是以前面的复杂网图为例，来讲解弗洛伊德(Floyd) 算法。
  首先我们针对下面网图准备两个矩阵 D−1D^{-1} 和 P−1P^{-1}，D−1D^{-1} 就是网图的邻接矩阵，P−1P^{-1} 初设为P[i][j]=j这样的矩阵，它主要用来存储路径。

  代码如下，注意因为是求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathtable[MAXVEX][MAXVEX];

/* Floyd算法，求网图G中各顶点v到其余顶点w最短路径P[v][W]及带权长度D[v][W] */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
	int v,w,k;
	for(v-0; v<G.numVertexes; ++v)	/* 初始化D与P */
	{
		for(w=0; w<G.numVertexes; ++w )
		{
			(*D)[v][w]=G.arc[v][w];	/* D[v][w]值即为对应点间的权值 */
			(*P)[v][w]=w;	/* 初始化P */
		}
	}
	for (k=0; k<G . numVertexes; ++k)
	{
		for (v=0; v<G.numVertexes; ++v)
		{
			for (w=0; w<G.numVertexes; ++w)
				if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
				{	/* 如果经过下标为k顶点路径比原两点间路径更短 */
					(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
					(*P)[v][w]=(*P)[v][k];	/* 路径设置经过下标为k的顶点 */
				}
			}
		}
	}
}
  1. 程序开始运行，第 5~12 行就是初始化了D和P，使得它们成为上图的两个矩阵。从矩阵也得到，v0_0→v1_1 路径权值是 1，v0_0→v2_2 路径权值是 5，v0_0→v3_3 无边连线，所以路径权值为极大值 65535。
  2. 第 13~26 行，是算法的主循环，一共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。
  3. 当K=0时，也就是所有的顶点都经过 v0_0 中转，计算是否有最短路径的变化。可惜结果是，没有任何变化，如下图所示。
  4. 当k=1时，也就是所有的顶点都经过 v1_1 中转。此时，当v=0时，原本D[0][2]=5，现在由于D[0][1]+D[1][2]=4。 因此由代码的第 20 行，二者取其最小值，得到D[0][2]=4，同理可得D[0][3]=8、 D[0][4]=6，当v=2、3、4时，也修改了一些数据，请参考如下图中虚线框数据。由于这些最小权值的修正，所以在路径矩阵P上，也要作处理，将它们都改为当前的P[v][k]值，见代码第 22 行。
  5. 接下来就是k=2一直到 8 结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D0D^{0} 是以 D−1D^{-1} 为基础，D−1D^{-1} 是以 D0D^{0} 为基础，···，D8D^{8} 是以 D7D^{7} 为基础，就像我们曾经说过的七个包子的故事，它们是有联系的，路径矩阵P也是如此。最终当k=8时，两矩阵数据如下图所示。

      至此，我们的最短路径就算是完成了，你可以看到矩阵第 v0_0 行的数值与迪杰斯特拉算法求得的D数组的数值是完全相同，都是 {0,1.4.7,5,8,10,12,16}。 而且这里是所有顶点到所有顶点的最短路径权值和都可以计算出。
      那么如何由P这个路径数组得出具体的最短路径呢？以 v0_0 到 v8_8 为例，从右上图第v8_8 列，P[0][8]=1，得到要经过顶点 v1_1,然后将 1 取代 0 得到P[1][8]=2，说明要经过 v2_2，然后将 2 取代 1 得到P[2][8]=4，说明要经过 v4_4，然后将 4 取代 2 得到P[4][8]=3，说明要经过 v3_3，···，这样很容易就推导出最终的最短路径值为v0_0→v1_1→v2_2→v4_4→v3_3→v6_6→v7_7→v8_8。
      求最短路径的显示代码可以这样写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (v=0; v<G.numVertexes; ++v)
{
	for (w=v+1; W<G.numVertexes; w++)
	{
		printf("v%d-v%d weight: %d ",v,w,D[v][w]);
		k=P[v][W];	/* 获得第一个路径顶点下标 */
		printf(" path:%d",v);	/* 打印源点 */
		while(k!=w)	/* 如果路径顶点下标不是终点 */
		{
			printf("-> %d",k);	/*打印路径顶点*/
			k=P[k][w];	/* 获得下一个路径顶点下标 */
		}
		printf(" -> %d\n",w);	/* 打印终点 */
	}
	printf("\n");
}

  再次回过头来看看弗洛伊德（Floyd）算法，它的代码简洁到就是一个二重循环初始化加一个三重循环权值修正，就完成了所有顶点到所有顶点的最短路径计算。几乎就如同是我们在学习C语言循环嵌套的样例代码而已。如此简单的实现，真是巧妙之极，在我看来，这是非常漂亮的算法，不知道你们是否喜欢？很可惜由于它的三重循环，因此也是 O(n3)O(n^3) 时间复杂度。如果你面临需要求所有顶点至所有顶点的最短路径问题时，弗洛伊德（Floyd）算法应该是不错的选择。
  另外，我们虽然对求最短路径的两个算法举例都是无向图，但它们对有向图依然有效，因为二者的差异仅仅是邻接矩阵是否对称而已。

2. 总结

  最短路径的现实应用非常多，我们也介绍了两种算法。迪杰斯特拉（Dijkstra）算法更强调单源顶点查找路径的方式，比较符合我们正常的思路，容易理解原理，但算法代码相对复杂。而弗洛伊德（Floyd）算法则完全抛开了单点的局限思维方式，巧妙地应用矩阵的变换，用最清爽的代码实现了多顶点间最短路径求解的方案，原理理解有难度，但算法编写很简洁。