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

  下面是求解该问题的伪代码，请填充其中空缺的 (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）（用Ο 符号表示）。 
   [答案讨论]

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