图的最短路径拓扑排序和关键路径

本文格式为Word版，下载可任意编辑——图的最短路径拓扑排序和关键路径数据结构课程辅导

图的最短路径、拓扑排序和关键路径

一、最短路径

由图的概念可知，在一个图中，若从一顶点到另一顶点存在着一条路径(这里只探讨无回路的简单路径)，则称该路径长度为该路径上所经过的边的数目，它也等于该路径上的顶点数减1。由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。

上面所述的图的最短路径问题只是对无权图而言的，若图是带权图，则把从一个顶点i到图中其余任一个顶点j的一条路径上所经过边的权值之和定义为该路径的带权路径长度，从vi到vj可能不止一条路径，我们把带权路径长度最短（即其值最小）的那条路径也称作最短路径，其权值也称作最短路径长度或最短距离。

例如，在图3-1中，从v0到v4共有三条路径：{0,4},{0,1,3,4}和{0,1,2,4}，其带权路径长度分别为30,23和38，可知最短路径为{0,1,3,4}，最短距离为23。

图3-1带权图和对应的邻接矩阵

1

实际上，这两类最短路径问题可合并为一类，这只要把无权图上的每条边标上数值为1的权就归属于有权图了，所以在以后的探讨中，若不特别指明，均认为是求带权图的最短路径问题。

求图的最短路径问题用途很广。例如，若用一个图表示城市之间的运输网，图的顶点代表城市，图上的边表示两端点对应城市之间存在着运输线，边上的权表示该运输线上的运输时间或单位重量的运费，考虑到两城市间的海拔高度不同，流水方向不同等因素，将造成来回运输时间或运费的不同，所以这种图寻常是一个有向图。如何能够使从一城市到另一城市的运输时间最短或者运费最省呢？这就是一个求两城市间的最短路径问题。

求图的最短路径问题包括两个方面：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行探讨。

1.从一顶点到其余各顶点的最短路径

对于一个具有n个顶点和e条边的图G，从某一顶点vi(称此为源点)到其余任一顶点vj(称此为终点)的最短路径，可能是它们之间的边(i,j)或，也可能是经过k个（1≤k≤n-2，最多经过除源点和终点之外的所有顶点）中间顶点和k+1条边所形成的路径。例如在图3-1中，从v0到v1的最短路径就是它们之间的有向边，其长度为3；从v0到v4的最短路径经过两个中间点v1和v3以及三条有向边,和，其长度为23。

那么，如何求出从源点i到图中其余每一个顶点的最短路径呢？狄克斯特拉(Dijkstra)于1959年提出了解决此问题的一般算法，具体做法是依照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度，每次求出从源点i到一个终点m的最短路径及长度后，都要以该顶点m作为新考虑的中间点，用vi到vm的最短路径和最短路径长度对vi到其它尚未求出最短路径的那些终点的当前最短路径及长度作必要地修改，使之成为当前新的最短路径和最短路径长度，当进行n-2次（因最多考虑n-2个中间点）后算法终止。

狄克斯特拉算法需要设置一个集合，假定用S表示，其作用是保存已

2

求得最短路径的终点序号，它的初值中只有一个元素，即源点i，以后每求出一个从源点i到终点m的最短路径，就将该顶点m并入S集合中，以便作为新考虑的中间点；还需要设置一个整型（假定权值类型为整型）数组dist[MaxVertexNum]，该数组中的第j个元素dist[j]用来保存从源点i到终点j的目前最短路径长度，它的初值为(i,j)或边上的权值，若vi到vj没有边，则权值为MaxValue，以后每考虑一个新的中间点时，dist[j]的值可能变小；另外，再设置一个与dist数组相对应的、类型为adjlist的邻接表表头向量数组path，该数组中的第j个元素path[j]指向一个单链表，该单链表中保存着从源点i到终点j的目前最短路径，即一个顶点序列，当vi到vj存在着一条边时，则path[j]初始指向由顶点i和j构成的单链表，否则path[j]的初值为空。

此算法的执行过程是：首先从S集合以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，查找出其值最小的元素，假定为dist[m]，该元素值就是从源点i到终点m的最短路径长度(证明从略)，对应path数组中的元素path[m]所指向的单链表链接着从源点i到终点m的最短路径，即经过的顶点序列或称边序列；接着把已求得最短路径的终点m并入集合S中；然后以vm作为新考虑的中间点，对S集合以外的每个顶点j，比较dist[m]+GA[m][j]（GA为图G的邻接矩阵）与dist[j]的大小，若前者小于后者，说明参与了新的中间点vm之后，从vi到vj的路径长度比原来变短，应用它替换dist[j]的原值，使dist[j]始终保持到目前为止最短的路径长度，同时把path[m]单链表复制到path[j]上，并在其后插入vj结点，使之构成从源点i到终点j的目前最短路径。重复n-2次上述运算过程，即可在dist数组中得到从源点i到其余每个顶点的最短路径长度，在path数组中得到相应的最短路径。为了简便起见，可采用一维数组s[n]来保存已求得最短路径的终点的集合S，具体做法是：若顶点j在集合S中，则令数组元素s[j]的值取1，否则取0。这样，当判断一个顶点j是否在集合S以外时，只要判断对应的数组元素s[j]是否为0即可。

例如，对于图3-1来说，若求从源点v0到其余各顶点的最短路径，则开始时三个一维数组s,dist和path的值为：

3

01234s10000dist03∞∞30pathv0,v1v0,v4

下面开始进行第一次运算，求出从源点v0到第一个终点的最短路径。首先从s元素为0的对应dist元素中，查找出值最小的元素，求得dist[2]的值最小，所以第一个终点为v1,最短距离为dist[2]=3，最短路径为path[2]={0,1}，接着把s[1]置为1，表示v1已参与S集合中，然后以v1为新考虑的中间点，对s数组中元素为0的每个顶点j（此时2≤j≤4）的目前最短路径长度dist[j]和目前最短路径path[j]进行必要地修改，因dist[1]+GA[1][2]=3+25=28，小于dist[2]=∞，所以将28赋给dist[2]，将path[1]并上v2后赋给path[2]，同理因dist[1]+GA[1][3]=3+8=11，小于dist[3]=∞，所以将11赋给dist[3]，将path[1]并上v3后赋给path[3]，最终再看从v0到v4，以v1作为新考虑的中间点的状况，由于v1到v4没有出边，所以GA[1][4]=∞，故dist[1]+GA[1][4]不小于dist[4]，因此dist[4]和path[4]无需修改，应维持原值。至此，第一次运算终止，三个一维数组的当前状态为：

01234s

11000dist

03281130path

v0,v1v0,v1,v2v0,v1,v3v0,v4

下面开始进行其次次运算，求出从源点v0到其次个终点的最短路径。首先从s数组中元素为0的对应dist元素中，查找出值最小的元素，求得dist[3]的值最小，所以其次个终点为v3,最短距离为dist[3]=11，最短路径为path[3]={0,1,3}，接着把s[3]置为1，然后以v3作为新考虑的中间点，对s中元素为0的每个顶点j（此时j=3,5）的dist[j]和path[j]进行必要的修改，因dist[3]+GA[3][2]=11+4=15，小于dist[2]=28，所以将15赋给dist[2]，将path[3]并上v2后赋给path[2]，同理，因

4

dist[3]+GA[3][4]=11+12=23，小于dist[4]=30，所以将23赋给dist[4]，将path[3]并上v4后赋给path[4]。至此，其次次运算终止，三个一维数组的当前状态为：

01234s

11010dist

03151123path

v0,v1v0,v1,v3,v2v0,v1,v3v0,v1,v3,v4

下面开始进行第三次运算，求出从源点v0到第三个终点的最短路径。首先从s中元素为0的对应dist元素中，查找出值最小的元素为dist[2]，所以求得第三个终点为v2，最短距离为dist[2]=15，最短路径为path[2]={0,1,3,2}，接着把s[2]置为1，然后以v2作为新考虑的中间点，对s中元素为0的每个顶点j（此时只有v4一个）的dist[j]和path[j]进行必要的修改，因dist[2]+GA[2][4]=15+10=25，大于dist[4]=23，所以无需修改，原值不变。至此，第三次运算终止，三个一维数组的当前状态为：

01234s11110dist0