軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2022/3/7）在線測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/3/7

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2022/3/7）

試題四
閱讀下列說明，回答問題1和問題2，將解答填入的對(duì)應(yīng)欄內(nèi)。
[說明]
現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市，使該城市的其他社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度。
現(xiàn)設(shè)計(jì)一個(gè)算法來找到該大型超市的最佳位置：即在給定圖中選擇一個(gè)頂點(diǎn)，使該頂點(diǎn)到其他各頂點(diǎn)的最短路徑之和最小。算法首先需要求出每個(gè)頂點(diǎn)到其他任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個(gè)頂點(diǎn)之間的最短路徑；然后對(duì)每個(gè)頂點(diǎn)，計(jì)算其他各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小的頂點(diǎn)作為建大型超市的最佳位置。
[問題1]
本題采用F10y-Warshall算法求解任意兩個(gè)頂點(diǎn)之間的最短路徑。已知圖G的頂點(diǎn)集合為

下面是求解該問題的偽代碼，請(qǐng)?zhí)畛淦渲锌杖钡?1)至(6)處。偽代碼中的主要變量說明如下：
W：權(quán)重矩陣
n：圖的頂點(diǎn)個(gè)數(shù)
SP：最短路徑權(quán)重之和數(shù)組，SP[i]表示頂點(diǎn)i到其他各頂點(diǎn)的最短路徑權(quán)重之和，i從1到n
min_SP：最小的最短路徑權(quán)重之和
min_V：具有最小的最短路徑權(quán)重之和的頂點(diǎn)
i：循環(huán)控制變量
j：循環(huán)控制變量
k：循環(huán)控制變量
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]中偽代碼的時(shí)間復(fù)雜度為  (7)  (用O符號(hào)表示)。