阅读下列说明,回答问题l和问题2,将解答填入答题纸的对应栏内。【说明】现需在某城市中选择一个社区

Question

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

【说明】

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

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

下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：

W：权重矩阵

n：图的顶点个数

sP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n

rain_SP：最小的最短路径权重之和

min_v：具有最小的最短路径权重之和的顶点

i：循环控制变量

j：循环控制变量

k：循环控制变量

LOCATE-SHOPPINGMALL(W，n)

1 D(0)=W

2 for(1)

3 for i=1 t0 n

4 for j=1 t0 n

5

6 (2)

7 else

8 (3)

9 for i=1 to n

10 sP[i] =O

11 for j=1 to n

12 (4)

13 min sP=sP[1]

14 (5)

15 for i=2 t0 n

16 if min sP>sP[i]

17 min sP=sP[i]

18 min V=i

19 return (6)

Answer 1

正确答案：(1) k=1 tO n (5)rain_v=1(6)min_v
(1) k=1 tO n (5)rain_v=1(6)min_v