搜题请搜索小程序“爱下问搜题”
问题 问答题

(A)


Directions: Translate the following sentences into English.

这里的菜烧得很好，还有免费蛋糕供应。

答案

参考答案：The dishes are well cooked here and free cakes are provided.

填空题

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

[说明]

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

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

[问题1]

本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V=1，2，…，n)，W=Wijn*n为权重矩阵。

设为从顶点i到顶点j的一条最短路径的权重。

当k=0时，不存在中间顶点，因此；当k＞0时，该最短路径上所有的中间顶点均属于集合1，2，…，k。

若中间顶点包括顶点k，则；若中间顶点不包括顶点k，则。

于是得到如下递归式：

因为对于任意路径，所有的中间顶点都在集合1，2，…，n内，因此矩阵给出了任意两个顶点之间的最短路径，即对所有i，j∈V，表示顶点i到顶点j的最短路径。

下面是求解该问题的伪代码，请填充其中的空缺(1)～(6)。

伪代码中的主要变量说明如下：

W：权重矩阵；

n：图的顶点个数；

SP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i取值为1～n；

min_SP：最小的最短路径权重之和；

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

i：循环控制变量；

j：循环控制变量；

k：循环控制变量。

LOCATE -SHC)PPINGNALL(W，n)

1 D(0)=W

2 for (1)

3 for i=1 to n

4 for j=1 to n

5 if

6 (2)

7 else

8 (3)

9 for i=1 to n

10 SP[i]=0

11 for j=1 to n

12 (4)

13 min_SP=SP[1]

14 (5)

15 for i=2 to n

16 if min_SP＞SP[i]

17 min_SP=SP[i]

18 min_v=i

19 return (6)

[问题2]

问题1中伪代码的时间复杂度为 (7) (用O符号表示)。

（6）处填（）。
查看答案
判断题

《望庐山瀑布》的作者是唐代诗人杜甫。
查看答案