1 数据结构课程辅导 ---图的最短路径、拓扑排序和关键路径 一、最 短 路 径 由图的概念可知，在一个图中，若从一顶点到另一顶点存在着一条路径(这里只讨论无回路的简单路径)，则称该路径长度为该路径上所经过的边的数目，它也等于该路径上的顶点数减 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 带权图和对应的邻接矩阵 2 实际上，这两类最短路径问题可合并为一类，这只要把无权图上的每条边标上数值为 1的权就归属于有权图了，所以在以后的讨论中，若不特别指明，均认为是求带权图的最短路径问题。 求图的最短路径问题用途很广。例如，若用一个图表示城市之间的运输网，图的顶点代表城市，图上的边表示两端点对应城市之间存在着运输线，边上的权表示该运输线上的运输时间或单位重量的运费，考虑到两城市间的海拔高度不同，流水方向不同等因素，将造成来回运输时间或运费的不同，所以这种图通常是一个有向图。如何能够使从一城市到另一城市的运输时间最短或者运费最省呢？这就是一个求两城市间的最短路径问题。 求图的最短路径问题包括两个方面：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行讨论。 1. 从一顶点到其余各顶点的最短路径 对于一个具有 n个顶点和e条边的图 G，从某一顶点 vi(称此为源点)到其余任一顶点 vj(称此为终点)的最短路径，可能是它们之间的边(i,j)或，也可能是经过k个（1≤k≤n-2，最多经过除源点和终点之外的所有顶点）中间顶点和k+1条边所形成的路径。例如在图 3-1中，从 v0到 v1的最短路径就是它们之间的有向边<0,1>，其长度为 3；从 v0到 v4的最短路径经过两个中间点v1和v3以及三条有向边 <0,1>...
