醫(yī)院選址問題 1. 問題描述 n個村莊之間的交通圖可以用有向網圖來表示，圖中邊上的權值表示從村莊i到村莊j的道路長度。現(xiàn)在要從這n個村莊中選擇一個村莊新建一所醫(yī)院，問這所醫(yī)院應建在哪個村莊，才能使所有的村莊離醫(yī)院都比較近？ 2. 基本要求 (1) 建立模型，設計存儲結構； (2) 設計算法完成問題求解； (3) 分析算法的時間復雜度。 3. 設計思想 醫(yī)院選址問題實際是求有向圖中心點的問題。首先定義頂點的偏心度。 設圖G=（V，E），對任一頂點k，稱E(k)=max{d(i, k)}（i∈V）為頂點k的偏心度。顯然，偏心度最小的頂點即為圖G的中心點。 如圖7(a)所示是一個帶權有向圖，其各頂點的偏心度如圖(b)所示。 醫(yī)院選址問題的算法用偽代碼描述如下： 1．對加權有向圖，調用Floyd算法，求每對頂點間最短路徑長度的矩陣； 2．對最短路徑長度矩陣的每列求大值，即得到各頂點的偏心度； 3．具有最小偏心度的頂點即為所求。 【思考題】圖的存儲結構和算法的設計需要一定的靈活性和技巧。從醫(yī)院選址問題的求解過程，你有什么感想？ 答：通過將圖存儲的方法很多，這兒用數(shù)組，簡單化數(shù)據(jù)，可以更好的編號和運行程序。