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