求解最短路径Dijkstra’s Algorithm

问题

在赋权连通图G中寻找点word/media/image1_1.png到点word/media/image2_1.png的最短路径。

求解

图论中最短路问题目前有两种模式，一种是single-source，另一种是all pairs.前一种关注的是从某一点到其他点的最短路径问题，起始点是固定的；后一种则强调任意两点间的最短路径问题，起始点和终止点都不固定。两个问题紧密联系，解决问题一，则我们不停变换起始点就可以解决问题二；反过来，解决问题二就解决了问题一，问题一此时是问题二的特例。然而，两者在时间复杂度上是有区别的，也就是说，用问题一的算法去解决问题二效率上并不那么高效，同时用问题二的算法去解决问题一也是不划算的。

Single-source shortest paths（单源最短路径）

给定了图G中起始点word/media/image3_1.png，我们要寻找从word/media/image3_1.png到其他点的最短路径。

1. Dijkstra’s Algorithm

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。值得注意的是，该算法要求图中不存在负权边，即对任意的边word/media/image4_1.png。其时间复杂度为word/media/image5_1.png。

算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用V-S表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点word/media/image3_1.png到S中各顶点的最短路径长度不大于从源点word/media/image3_1.png到V-S中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从word/media/image3_1.png到此顶点的最短路径长度，V-S中的顶点的距离，是从word/media/image3_1.png到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

算法步骤：

a.初始时，S只包含源点，即S＝{word/media/image3_1.png}，word/media/image3_1.png的距离为0。V-S包含除word/media/image3_1.png外的其他顶点，即V-S={其余顶点}，若word/media/image3_1.png与V-S中顶点u有边，则word/media/image3_1.png>正常有权值，若u不是word/media/image3_1.png的出边邻接点，则word/media/image3_1.png>权值为∞。

b.从V-S中选取一个距离word/media/image3_1.png最小的顶点k，把k，加入S中（该选定的距离就是word/media/image3_1.png到k的最短路径长度）。

c.以k为新考虑的中间点，修改V-S中各顶点的距离；若从源点word/media/image3_1.png到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值等于顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

示例：（MATLAB程序见附录1）

权重矩阵为word/media/image6_1.png，测试结果：

2. Bellman-Ford Algorithm

与Dijkstra’s algorithm算法相比较，Bellman-Ford Algorithm的优点就是它能够处理图中存在负权的情况，若图中存在负圈，它将给出提示。当然它的复杂度就要高一些，为word/media/image9_1.png。

算法思想：首先可以确定的是，图G的任意一条最短路径既不能包含负权值回路，也不能包含正权值回路，因此它最多包含(|v|-1)条边。从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这颗最短路径树的过程：

a) 在对每条边进行第一遍松弛的时候，生成了从s出发，层次至多为1的那些树枝，也就是说找到了与s至多有1条边相连的那些顶点的最短路径；

b) 在对每条边进行第二遍松弛的时候，生成了从s出发，层次至多为2的那些树枝，也就是说找到了与s至多有2条边相连的那些顶点的最短路径；

... ...以此类推；

因为最短路径最多包含(|v|-1)条边，所以只需循环(|v|-1)次。

Bellman-Ford算法构造一个最短长度数组序列word/media/image10_1.png，word/media/image11_1.png，word/media/image12_1.png，... ，word/media/image13_1.png。其中：word/media/image10_1.png为从源点s到终点u的只经过1条边的最短路径长度，并有word/media/image14_1.png；word/media/image11_1.png为从源点s到终点u的最多经过2条边的最短路径长度；word/media/image12_1.png为从源点s到终点u的最多经过不构成负权值回路的3条边的最短路径长度；... ... word/media/image13_1.png为从源点s到终点u的最多经过不构成负权值回路的n-1条边的最短路径长度；算法的最终目的是计算出word/media/image13_1.png，为源点s到u的最短路径长度。