2009年上半年软考软件设计师下午试卷[7]

  试题四 （共15 分 ）

  阅读下列说明，回答问题1和问题2，将解答填入答题纸的对应栏内。

  【说明】

  现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。

  现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。

  【问题 1】（12 分）

  本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。 已知图G的顶点集合为V= {1,2,...,n } ，W= ｛W_ij｝_n*n 为权重矩阵。设 d ^(k)_ij=为从顶点i到顶点j的一条最短路径的权重。当k = 0时，不存在中间顶点，因此d⁽⁰⁾_ij=w_ij

  当k >0 时，该最短路径上所有的中间顶点均属于集合 {1,2, ..., k｝若中间顶点包括顶点 k ，则d^(k)_ij=d^(k-1)_ik+d^(k-1)_kj若中间顶点不包括顶点k ，则d^(k-1)_ij=d^(k-1)_ij

  于是得到如下递归式。

  因为对于任意路径，所有的中间顶点都在集合{1,2, ..., n｝ 内，因此矩阵D⁽ⁿ⁾ =｛d⁽ⁿ⁾_ij｝_n*n 给出了任意两个顶点之间的最短路径，即对所有i, j ∈V,d(n)ij表示顶点i到顶点 j的最短路径。 

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]  [11]