摘要:下面是求解该问题的伪代码,请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下:W:权重矩阵n:图的顶点个数SP:最短路径权重之和数组,SP[i]表示顶点i到其它各顶点的最短路径权重之和,i从1到nmin_SP:最小的最短路径权重之和min_v:具有最小的最短路径权重之和的顶点i:循环控制变量j:循环控制变量k:循环控制变
下面是求解该问题的伪代码,请填充其中空缺的 (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
5 if d(k-1)ij≤≤d(k-1)ik+d(k-1)kj
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】(3 分)
【问题3】中伪代码的时间复杂度为(7)(用Ο 符号表示)。
[答案讨论]
软考备考资料免费领取
去领取