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

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

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

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

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

閱讀下列說明，回答問題1和問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。 
【說明】 
現(xiàn)需在某城市中選擇一個社區(qū)建一個大型超市，使該城市的其它社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度。現(xiàn)設(shè)計(jì)一個算法來找到該大型超市的最佳位置：即在給定圖中選擇一個頂點(diǎn)，使該頂點(diǎn)到其它各頂點(diǎn)的最短路徑之和最小。算法首先需要求出每個頂點(diǎn)到其它任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個頂點(diǎn)之間的最短路徑；然后對每個頂點(diǎn)，計(jì)算其它各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小的頂點(diǎn)作為建大型超市的最佳位置。
【問題1】（12分）  
本題采用Floyd-Warshall算法求解任意兩個頂點(diǎn)之間的最短路徑。 已知圖G 的頂點(diǎn)集合為V= {1，2，...，n } ，W= ｛Wij｝n*n 為權(quán)重矩陣。設(shè) d (k)ij=為從頂點(diǎn)i到頂點(diǎn) j的一條最短路徑的權(quán)重。當(dāng)k = 0時，不存在中間頂點(diǎn)，因此d(0)ij=wij當(dāng)k >0 時，該最短路徑上所有的中間頂點(diǎn)均屬于集合 {1，2， ...， k｝若中間頂點(diǎn)包括頂點(diǎn) k ，則d(k)ij=d(k-1)ik+d(k-1)kj若中間頂點(diǎn)不包括頂點(diǎn)則d(k-1)ij=d(k-1)i于是得到如下遞歸式

因?yàn)閷τ谌我饴窂?，所有的中間頂點(diǎn)都在集合{1，2， ...， n｝ 內(nèi)，因此矩陣D(n)=｛d(n)ij｝n*n 給出了任意兩個頂點(diǎn)之間的最短路徑，即對所有i， j ∈V，d(n)ij表示頂點(diǎn)i到頂點(diǎn) j的最短路徑。 
下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?(1)至(6)處。 偽代碼中的主要變量說明如下： 
W：權(quán)重矩陣 
n： 圖的頂點(diǎn)個數(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)控制變量 

【問題2】（3分）
【問題1】中偽代碼的時間復(fù)雜度為（7）用Ο 符號表示）。
信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/380806315.html

信管網(wǎng)考友試題答案分享：

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/st/380806315.html