軟件設計師案例分析當天每日一練試題地址：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：www.jazzmuze.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/8/26）在線測試：www.jazzmuze.com/exam/ExamDayAL.aspx?t1=4&day=2022/8/26

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內容（2022/8/26）

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

因為對于任意路徑，所有的中間頂點都在集合{1，2， ...， n｝ 內，因此矩陣D(n)=｛d(n)ij｝n*n 給出了任意兩個頂點之間的最短路徑，即對所有i， j ∈V，d(n)ij表示頂點i到頂點 j的最短路徑。
下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?(1)至(6)處。 偽代碼中的主要變量說明如下：
W：權重矩陣
n： 圖的頂點個數(shù)
SP：最短路徑權重之和數(shù)組，SP[i]表示頂點i到其它各頂點的最短路徑權重之和，i從1到n
min_SP：最小的最短路徑權重之和
min_v：具有最小的最短路徑權重之和的頂點
i：循環(huán)控制變量
j：循環(huán)控制變量
k：循環(huán)控制變量

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

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

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