【题21】设计公共汽车线路3--试题解析

现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路

造价，县城所在的城镇为v0。由于该县的经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程的总造价必须最少。 输入：

n (城市数，1≤n≤20) 县城所在的城镇序号v0 e (有向边数1≤e≤210)

以下e行，每行为3个整数，两个城镇的序号和它们间的公路造价 输出：

k行，每行为一条通往县城的汽车线路的总造价和该条线路途径的城镇序号

分析：

设G=（V，E）是一个有向图，它的每一条边（U，V）∈Ｅ都有一个权W（U，V），在G中指定一个结点V0，要求把从V0到G的每一个结点Vj(VＪ∈Ｖ)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0不可达Vj）。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组，每一个结点对应一个距离值

第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至

此结点的最短路径长度；

我们按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。具体作法是：

初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）

w0i disti(v0,vi)E(v0,vi)E

然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：

若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值>vm的距离值+Wmi），则要修改vi

的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。下面，我们来证明这个算法：

由于初始时对两个组的划分及各结点距离值的确定符合上述基本思想，因此要证明算法正确性，关键是证明每次往第一组加入结点vm后，其两个组的划分及结点距离值仍然符合要求。也就是要证明第二组中距离值最小的结点vm，其距离值为v0到vm的最短路径长度，且该路径长度在v0至第二组结点的所有路径中最短的。我们来证明这两点：

⑴ 若vm的距离值不是从v0到vm的最短路径长度，另有一条v0经由第二组某些结点（其中第一个结点设为vs）到达vm的路径，其长度比vm的距离值更小，即

vs的距离值与vm是第二组中距离值最小的结点矛盾。所以vm的距离值就是从v0到vm的最短路径长度。

⑵设vx是第二组中除vm外的任何其它结点。若v0至vx的最短路径上的中间结点为第一组的结点，由距离值的定义可知，其路径长度势必大于等于v0至vm的最短路径长度；若v0至vx的最短路径不仅包含第一组的结点为中间结点。设路径上第一个在第二组的中间结点为vy，则v0至vy的路径长度就是vy的距离值，已大于等于v0至vm的最短路径长度，那么v0到vx的最短路径长度当然也不会小于v0到vm的最短路径长度了，所以v0到vm的路径长度在v0至第二组结点的所有路径中是最短的。设

n—图的结点数；

adj—有向图的相邻矩阵。其中

dist—最短路径集合。其中

dist[i]．pre—在v0至vi的最短路径上，vi的前趋结点序号； dist[i]．length—v0至vI的最短路径长度，即vi的距离值； （1≤i≤n） Const n=图的结点数； Type

path=record {路径集合的结点类型} length：real； {距离值} pre：0‥n； {前趋结点序号} end； var

adj：array[1‥n，1‥n] of real {相邻矩阵} dist：array[1‥n] of path； {路径集合} 计算单源最短路径的过程如下：

fillchar(adj，sizeof(adj)，0)； {建立相邻矩阵adj} for i←1 to n do for j←1 to n do

if（i，j）∈E then adj[i，j]←wij else adj[i，j]←∞；

for i←1 to n do {路径集合初始化} begin

dist[i]．length←adj[v0，i]； if dist[i]．length<>∞ then dist[i]．pre←v0 else dist[i]．pre←0； end；{for}

adj[v0，v0]←1； {源结点v0进入第一组} repeat

min←∞； u←0；

for i←1 to n do {从第二组中找距离值最小的结点u} if (adj[i，i]=0)and(dist[i]．lengthu←i； min←dist[i]．length； end；{then}

if u<>0 {第二组中存在一个距离值最小的结点} then begin

adj[u，u]←1； {结点u进入第一组} for i←1 to n do {修正第二组中u可达的结点距离值}

if (adj[i，i]=0)and(dist[i]．length>dist[u]．length+adj[u，i]) then begin

dist[i]．length←dist[u]．length+adj[u，i]； dist[i]．pre←u； end；{then} end；{then}

until u=0； {直至n个结点全部加入第一组为止}

Dijkstra算法的时间复杂度为W（n2）。算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi

的最短路径：

procedure print(i：integer)； begin

if i=v0 then 输出结点v0 else begin

print(dist[i]．pre)；

输出结点i和v0至vi的最短路径长度dist[i]．length； end；{else} end；{print}

显然递归调用print[1]，…，print[n]后，可得知v0至所有结点的最短路径。由此得出主程序：

输入城镇数n；

输入出发城镇序号v0； 输入城镇间的距离矩阵w； 计算单源最短路径方案dist；

for i←1 to n do {枚举除v0外的其它城镇} begin

if (i<>v0 )and(dist[i]．length<>∞){若城镇i与城镇v0间有通路，则输出它们之间的最短距离和路径方案}

then begin wrtiln(dist[i]．length)；print(i)；end；{then} wrteln； end；{for}