信管网每日一练

软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2021/12/30）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2021/12/30

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2021/12/30）

试题四
阅读下列说明，回答问题1和问题2，将解答填入的对应栏内。
[说明]
现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。
[问题1]
本题采用F10y-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为

下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：
W：权重矩阵
n：图的顶点个数
SP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n
min_SP：最小的最短路径权重之和
min_V：具有最小的最短路径权重之和的顶点
i：循环控制变量
j：循环控制变量
k：循环控制变量
LOCATE   -SHOPPINGMALL (W, n)
1    D(0) = W
2    for   (1)
3       for i = 1 to n
4          for j = 1 to n



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[i]
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符号表示)。