試題四 （共15 分 ）

  閱讀下列說明，回答問題1和問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。

  【說明】

  現(xiàn)需在某城市中選擇一個社區(qū)建一個大型超市，使該城市的其它社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度。

  現(xiàn)設(shè)計一個算法來找到該大型超市的最佳位置：即在給定圖中選擇一個頂點，使該頂點到其它各頂點的最短路徑之和最小。算法首先需要求出每個頂點到其它任一頂點的最短路徑，即需要計算任意兩個頂點之間的最短路徑；然后對每個頂點，計算其它各頂點到該頂點的最短路徑之和；最后，選擇最短路徑之和最小的頂點作為建大型超市的最佳位置。

  【問題 1】（12 分）

  本題采用Floyd-Warshall算法求解任意兩個頂點之間的最短路徑。 已知圖G的頂點集合為V= {1,2,...,n } ，W= ｛W_ij｝_n*n 為權(quán)重矩陣。設(shè) d ^(k)_ij=為從頂點i到頂點j的一條最短路徑的權(quán)重。當k = 0時，不存在中間頂點，因此d⁽⁰⁾_ij=w_ij

  當k >0 時，該最短路徑上所有的中間頂點均屬于集合 {1,2, ..., k｝若中間頂點包括頂點 k ，則d^(k)_ij=d^(k-1)_ik+d^(k-1)_kj若中間頂點不包括頂點k ，則d^(k-1)_ij=d^(k-1)_ij

  于是得到如下遞歸式。

  因為對于任意路徑，所有的中間頂點都在集合{1,2, ..., n｝ 內(nèi)，因此矩陣D⁽ⁿ⁾ =｛d⁽ⁿ⁾_ij｝_n*n 給出了任意兩個頂點之間的最短路徑，即對所有i, j ∈V,d(n)ij表示頂點i到頂點 j的最短路徑。 

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